Let us call a state of the grid good when each row contains exactly \(A_i\) 1s. Here, we assume that the process continues even after a good state.

Let us define \(f_n=(\) the probability of having a good state after \(n\) operations when starting from the given state in input \()\). Additionally, let \(F(x)=\sum_{0 \leq n} f_n x^n\) be the generating function of \(f_n\).

Similarly, let us define \(g_n=(\) the probability of having a good state after \(n\) operations when starting from a good state \()\). (Note that \(g\) can be defined without depending on the initial good state.) Additionally, let \(G(x)=\sum_{0 \leq n} g_n x^n\) be the generating function of \(g_n\).

Finally, let us define \(e_n=(\) the probability of having the first good state after \(n\) operations when starting from the given state in input \()\). (Note that \(g\) can be defined without depending on the initial good state.) Additionally, let \(E(x)=\sum_{0 \leq n} e_n x^n\) be the generating function of \(e_n\).

Here, the relation \(E(x)G(x)=F(x)\) holds. Additionally, our final objective in this problem, \(\sum_{0 \leq n} n \times e_n\), can be obtained by substituting \(x=1\) in \(E'(x)\). (※)

Eventually, it is enough to find \(F\) and \(G\). Below, we describe how to find \(F\). (\(G\) can be found similarly.)

We will first find the exponential generating function \(F_{exp}(x)=\sum_{0 \leq n} f_n/n!\ x^n\).

Let us fix a good state and consider the probability of coinciding with it. Then, there will be a requirement for each square to be flipped an even/odd number of times. Using the generating function \(w_{even}(x)=(exp(x/HW)+exp(-x/HW))/2\) corresponding to a square flipped an even number times and the generating function \(w_{odd}(x)=(exp(x/HW)-exp(-x/HW))/2\) corresponding to a square flipped an odd number times, the sought generating function is their multiplication.

We have solved the case with a fixed good state. To deal with all possible good states, DP can be used. (The key in DP should be the degree of \(w_{even}\), and the value should be the number of good states corresponding to that generating function.)

Here, we find the exponential generating function as a multiplication of \(w_{even},w_{odd}\), but it can also be written as a linear combination of \(exp(ax)\), where \(a\) can take the values \(-HW/HW,-(HW-2)/HW,\cdots,(HW-2)/HW,HW/HW\).

Now we have found \(F_{exp}(x)\). Additionally, \(F(x)\) can also be found by making the terms corresponding to \(exp(ax)\) \(1/(1-ax)\).

We will find \(G\) similarly. There is a term \(1/(1-x)\) in \(F(x),G(x)\), which is a problem when substituting \(x=1\), so we choose to compute \(E(x)=((1-x)F(x))/((1-x)G(x))\). What remains is to find \((1-x)F(x)\), \((1-x)G(x)\), and substituting \(x=1\) in the derivatives of these.

Since \((1-x)/(1-ax)\) and the result of substituting \(x=1\) in the derivative can be computed by a simple formula, all sought values can be found as their linear combinations.

By the way, we can see that the results of substituting \(x=1\) in \((1-x)F(x)\) and \((1-x)G(x)\) are the same, which helps simplify the implementation a bit.

Our solution runs in, for example, \(O(H^2W^2)\) time.

Sample submission (c++)

(※) Here is a supplementary explanation for the validity of this substitution. First, the convergence of \(\sum_{1 \leq n} n \times e_n\) can be seen as a property of Absorbing Markov Chain. Thus, the radius of convergence of the power series \(\sum_{1 \leq n} n \times e_n\ x^{n-1}\) is at least \(1\). Therefore, in the range \(|x|<1\), this series coincides with the regular analytic function \(E'(x)\), and it follows from Abel’s theorem that the substitution \(x=1\) is also allowed (in the rational expression, not the series).