This is a user editorial. The official editorial says “with a more careful observation on the property of the problem, it can also be solved in about \(\mathrm{O}(HW \text{poly}(\log(HW)))\) time, but we will omit the details.” Here, we will explain that solution.

It is optimal to advance a piece that does not face another one square by one. Let \(X\) and \(Y\) be the sum of times that the first and second player can make such a move, respectively.

In the other rows where pieces face each other (let us call such rows “Nim rows”), the play Nim.

The outcome of the game is as follows:

• If the first player would win if there were only the Nim part
• If $X \le Y$, the first player will win
• If $X < Y$, the second player will win
• If the second player would win if there were only the Nim part
• If $X < Y$, the first player will win
• If $X \ge Y$, the second player will win

Let \(A_i\) and \(B_i\) be the number of initial states consisting of \(i\) Nim rows in which the first and second players will win, respectively. Also, let \(P_i\), \(Q_i\), and \(R_i\) be the number of initial states consisting of \(i\) non-Nim rows such that \(X<Y\), \(X=Y\), and \(X>Y\), respectively.

The solution is \(\sum_{i=0}^{H} \binom{H}{i}(A_i(Q_i+R_i)+B_iR_i)\). Here, note that \(P_i=R_i\) by symmetry. Since we can easily find the value \(\sum_{i=0}^{H} \binom{H}{i}(A_i+B_i)(P_i+Q_i+R_i)\), we can solve the problem if we can find \(\sum_{i=0}^{H} \binom{H}{i} (A_i-B_i) Q_i\).

The values of \(A_i\) and \(B_i\) can be found by Hadamard conversion in a total of \(\mathrm{O}(HW\log W)\) time. Let \(C_i = \binom{H}{i}(A_i - B_i)\).

The values of \(Q_i\) equal \([x^0] f(x)^i\) for such \(f\) that “\([x^i]f(x)=\) the number of initial states with exactly one non-Nim row such that \(X-Y=i\).”

Thus, we can find the answer if we can find \([x^0]\sum_{i=0}^{H} C_i f(x)^i\). Here, \([x^{-i}]f(x)=[x^i]f(x)\), so there exists a polynomial \(g(x)\) such that \(g(x+1/x)=f(x)\). Such \(g\) can be found in a total of \(\mathrm{O}(W^2)\) by inspecting the higher order of \(f\) to the lower.

Now consider finding \(\sum_{i=0}^{H} C_i g(x)^i\). This can be found in a total of \(\mathrm{O}(HW(\log H+\log W)\log H)\) time in a binary-tree manner. The coefficient of \([x^{2K}]\) in this polynomial multiplied by \(\binom{2K}{K}\) equals \([x^0]\sum_{i=0}^{H} C_i f(x)^i\).

Therefore, the problem has been solved in a total of \(\mathrm{O}(HW(\log H+\log W) \log H+HW^2)\) time.

Sample code https://atcoder.jp/contests/abc265/submissions/34139650