部分点解法

\(dp\lbrack n\rbrack\lbrack i\rbrack\lbrack j\rbrack\) を, 左から \(n\) 列目まで \(0,1,2\) の配置を決定して, 左から \(n\) 列目の上から \(i\) 行目までが \(0\), 上から \(j\) 行目までが \(1\) であるような配置の通り数とします.
\(dp\lbrack n\rbrack\lbrack i\rbrack\lbrack j\rbrack\) から \(dp\lbrack n+1\rbrack\lbrack k\rbrack\lbrack l\rbrack\) への遷移が可能であるかの判定は \(O(1)\) で出来るため, 計算量は全体で \(O(H^4W)\) です.

満点解法

いくつかの場合に分けて求めていきます.

\(1\) を使わない場合

\(0\) と \(2\) が隣り合わないことから, 全て \(0\) を書きこむ又は全て \(2\) を書きこむかの \(2\) 通りです.

\(1\) を使う場合　

まず特別な設定を付した状態で考えて, その後一般の場合を考えます.

左下,右上のマスにともに \(1\) を書く場合

この時, 以下の図のように,

• \(0,1,2\) の書きこみ方
• 「左下のマスの左上の頂点から右上のマスの左上の頂点へ, 辺に沿って移動する時の最短経路」と「左下のマスの右下の頂点から右上のマスの右下の頂点へ, 辺に沿って移動する時の最短経路」の組で, 頂点を共有しないもの

は1対1対応します.

よって, 求める場合の数はLGV公式によって

\[\begin{aligned} &\det \begin{pmatrix} \binom{H+W-2}{H-1}&\binom{H+W-2}{H}\\[3mm] \binom{H+W-2}{W}&\binom{H+W-2}{H-1}\\ \end{pmatrix} =&\frac{(H+W-2)!(H+W-1)!}{H!W!(H-1)!(W-1)!} \end{aligned}\]

と求まります. 但し, \(0!=1\) とし, \(n<k\) の時 \(\binom{n}{k}=0\) としています.

一般の場合

\(1\) を使うことから, ある \(1\le h_1\le h_2\le H\) 及び \(1\le w_1\le w_2\le W\) をなる整数の組 \((h_1,h_2,w_1,w_2)\) で, 以下を全て満たすものが一意的に存在します.

• \(X_{h_1,w_2}=X_{h_2,w_1}=1\)
• \(X_{h,w}=1\Rightarrow h_1\le h\le h_2\) かつ \(w_1\le w\le w_2\)

この時, \((h_1,w_1),(h_1,w_2),(h_2,w_1),(h_2,w_2)\) の \(4\) マスを四隅にもつ, マス目にそった長方形は, 必ず少なくとも \(2\) 辺以上をマス目の最も外側の辺と共有することが容易に分かります.

さらに, その定め方からこの長方形の外部に書かれる数は組 \((h_1,h_2,w_1,w_2)\) 毎に一意的に定まります.

よって,

• \(0,1,2\) の書き込み方
• \(1\le h_1\le h_2\le H\) 及び \(1\le w_1\le w_2\le W\) なる整数の組 \((h_1,h_2,w_1,w_2)\) であって, \((h_1,w_1),(h_1,w_2),(h_2,w_1),(h_2,w_2)\) の \(4\) マスを四隅にもつ長方形を考えると少なくとも \(2\) 辺以上をマス目の最も外側の辺と重なるもの, 及び \(X_{h_1,w_2}=X_{h_2,w_1}=1\) を満たすような, 長方形内部への \(0,1,2\) の数の書き込み方. 　

は \(1\) 対 \(1\) に対応します.
よって, とりうる長方形を全て試し, 「左下,右上のマスにともに \(1\) を書く場合」での式を適用すれば求めていた答えが得られます.

高速化

しかし, 長方形として取りうるものは \(O((H+W)^2)\) 個あるため, このままでは 実行制限時間に間に合いません.

そこで, 長方形内部への数の書き込み方が長方形の行数, 列数のみに依存することを用いて高速化をします.

まず長方形の高さが \(H\) の場合, 長方形の幅として考えられるものは \(W\) 種類のため, 全て試すことができます.

長方形の幅が \(W\) の場合も同様です.

最後に長方形の高さが \(H\) 未満で, 幅が \(W\) 未満の場合です. 長方形の高さ+幅の値でまとめて数えることを考えれば, 長方形内部への書き込み方は畳み込みで求まる形をしているため, 高速に計算できます.
よって, \(O((H+W)^2)\) 個の長方形に対する総和が, \(O((H+W)\log{(H+W)})\) で求まります.

以上により \(O((H+W)\log{(H+W)})\) でこの問題を解くことが出来ました.