各行について 1 の個数が \(A_i\) 個である状態を，よい状態と呼ぶことにします． ここでは，よい状態になっても操作が続くものとして考えます．

\(f_n=(\) 入力された状態から始めて，\(n\) 回操作を行った結果，よい状態になっている確率\()\) と定義します． また，その母関数を \(F(x)=\sum_{0 \leq n} f_n x^n\) とします．

同様に，\(g_n=(\) よい状態から始めて，\(n\) 回操作を行った結果，よい状態になっている確率\()\) と定義します．（始状態として選ぶよい状態に依らずに \(g\) が定まることに注意） また，その母関数を \(G(x)=\sum_{0 \leq n} g_n x^n\) とします．

最後に，\(e_n=(\) 入力された状態から始めて，\(n\) 回操作を行った結果，初めてよい状態になっている確率\()\) と定義します． また，その母関数を \(E(x)=\sum_{0 \leq n} e_n x^n\) とします．

ここで，\(E(x)G(x)=F(x)\) という関係式が成り立ちます． また，この問題で最終的に求めたい値は \(\sum_{0 \leq n} n \times e_n\) ですが，これは \(E'(x)\) に \(x=1\) を代入した値になります．（※）

結局，\(F,G\) を求められればよいことになります． 以下では，\(F\) の計算方法を解説します．（\(G\) も同様にできます）

まず，指数型母関数 \(F_{exp}(x)=\sum_{0 \leq n} f_n/n!\ x^n\) を求めてみます．

よい状態を一つ固定し，その状態に完全に一致する確率を考えてみます． すると，各マスに対して，偶数回/奇数回だけ flip されるという条件が発生します． 偶数回 flip されるマスに対応する母関数 \(w_{even}(x)=(exp(x/HW)+exp(-x/HW))/2\)，奇数回 flip されるマスに対応する母関数 \(w_{odd}(x)=(exp(x/HW)-exp(-x/HW))/2\) を用いると，それらを乗算したものが求めるべき母関数です．

よい状態を一つ固定した場合が解けましたが，よい状態としてありうるものすべてを考えるには DP をすればよいです． （DP のキーを \(w_{even}\) の次数とし，値はその母関数に対するよい状態の個数とすればよいです．）

今，\(w_{even},w_{odd}\) の積の形で指数型母関数を求めましたが，これは \(exp(ax)\) の線形和の形でも書けます． ここで，\(a\) として取りうる値は \(-HW/HW,-(HW-2)/HW,\cdots,(HW-2)/HW,HW/HW\) です．

よって，\(F_{exp}(x)\) が求まりました．そして，\(exp(ax)\) に対応する項を \(1/(1-ax)\) にすることで，\(F(x)\) も求まります．

同様にして \(G\) を求めます． \(F(x),G(x)\) には \(1/(1-x)\) という項が存在しており，これが \(x=1\) の代入の際に問題となります． そこで，\(E(x)=((1-x)F(x))/((1-x)G(x))\) と計算することにします． あとは \((1-x)F(x),(1-x)G(x)\) およびそれらの微分に \(x=1\) を代入したものを求めればよいです．

\((1-x)/(1-ax)\) およびその微分に \(x=1\) を代入した結果は簡単な式で計算できるため，それらの線形和で求めたい値もすべて求まります．

ところで，\((1-x)F(x)\) および \((1-x)G(x)\)に \(x=1\) を代入した結果は同じになることが分かるので，これを用いると少しだけ実装が簡潔になります．

計算量は \(O(H^2W^2)\) などです．

解答例(c++)

（※）この代入の正当性について補足します． まず，\(\sum_{1 \leq n} n \times e_n\) が収束することは，Absorbing Markov Chain の性質としてわかります． よって冪級数 \(\sum_{1 \leq n} n \times e_n\ x^{n-1}\) の収束半径は \(1\) 以上となります． よって，\(|x|<1\) の範囲ではこの級数は正則関数 \(E'(x)\) と一致し，アーベルの連続性定理 より \(x=1\) でも（級数ではなく有理式への）代入操作を考えてよいとわかります．