ユーザー解説です。公式解説で「より丁寧に考察を進めると \(\mathrm{O}(HW\mathrm{poly}(\log(HW)))\) 程度の計算量で解くこともできますがここでは割愛します。」と書かれているこの解法について解説します。

香車が向かい合っていない行は明らかに \(1\) マスずつ動かすことが最適です。この部分について先手が操作することのできる回数の総和を \(X\)、後手が操作することのできる回数の総和を \(Y\) とします。

香車が向かい合っているところでは Nim が行われます。

このゲームの勝敗は以下のようになります。

• Nim の部分だけがあった場合の勝者が先手の場合
• $X \le Y$ ならば先手の勝ち
• $X < Y$ ならば後手の勝ち
• Nim の部分だけがあった場合の勝者が後手の場合
• $X < Y$ ならば先手の勝ち
• $X \ge Y$ ならば後手の勝ち

Nim が行われる行のみが \(i\) 個ある場合、Nim で先手の勝つ初期盤面の個数を \(A_i\)、後手の勝つ初期盤面の個数を \(B_i\) とします。また、香車が向かい合っていない行が \(i\) 個ある場合、\(X<Y\) となる初期盤面の個数を \(P_i\)、\(X=Y\) となる初期盤面の個数を \(Q_i\)、\(X>Y\) となる初期盤面の個数を \(R_i\) とします。

解は \(\sum_{i=0}^{H} \binom{H}{i}(A_i(Q_i+R_i)+B_iR_i)\) となります。ここで、対称性より \(P_i=R_i\) であることに注目します。\(\sum_{i=0}^{H} \binom{H}{i}(A_i+B_i)(P_i+Q_i+R_i)\) の値は簡単に求めることができるため、\(\sum_{i=0}^{H} \binom{H}{i} (A_i-B_i) Q_i\) を求めることができれば解を求めることができます。

\(A_i,B_i\) の値はアダマール変換を行うことにより、 \(\mathrm{O}(HW\log W)\) で求めることができます。\(C_i = \binom{H}{i}(A_i - B_i)\) と置きます。

\(Q_i\) の値は、「\([x^i]f(x)=1\) 行だけ香車が向かい合っていない行があるとき、\(X-Y=i\) となる初期盤面の個数」となる \(f\) に対し、\([x^0] f(x)^i\) と等しいです。

よって、\([x^0]\sum_{i=0}^{H} C_i f(x)^i\) を求めることができれば解を求めることができます。ここで、\([x^{-i}]f(x)=[x^i]f(x)\) であることより、ある多項式 \(g(x)\) が存在し、\(g(x+1/x)=f(x)\) となります。この \(g\) は \(f\) を高次から見ることにより \(\mathrm{O}(W^2)\) などで求めることができます。

\(\sum_{i=0}^{H} C_i g(x)^i\) を求めることを考えます。これは二分木のように計算することにより \(\mathrm{O}(HW(\log H+\log W)\log H)\) で求めることができます。この多項式の \([x^{2K}]\) の係数に \(\binom{2K}{K}\) をかけた値の総和が \([x^0]\sum_{i=0}^{H} C_i f(x)^i\) となります。

よって、この問題を \(\mathrm{O}(HW(\log H+\log W) \log H)\) で解くことができます。

実装例 https://atcoder.jp/contests/abc265/submissions/34139650