ARC136-F Flip Cells 別解

問題

atcoder.jp

概要は省略します。

求める答えを S とします。 終了状態としてあり得る M = \prod_{i=1}^H \binom{W}{A_i} 個の状態を \Psi_1, \ldots, \Psi_M とします。

終了条件を除いて操作したとき、はじめて \Psi_i となるまでの回数の期待値を E'_i とします。

終了したときに \Psi_i となっている確率を P_i とします。

終了するまでの回数の期待値のうち、 \Psi_i で終わったときの寄与を E_i とします。

S = \sum E_i です。

C_{ij} を \Psi_i からはじめて \Psi_j に初めてなるまでの操作回数の期待値とすると、

\begin{align} E_i = E'_i - \sum _ {j \neq i} \left(P_j C _ {ji} + E_j \right) \end{align}

が成り立ちます。 両辺 i について総和を取ると

\begin{align} S = \sum E' _ i - (M-1)S - \sum _ {j \neq 1} C_{1j} \end{align}

となります。 ここで、対称性から i によらず \sum C _ {ij} が等しいことと \sum P_i = 1 を用いました。

C, E' を求めるときに必要な情報は、終了状態と今いくつマスの状態が一致しているかのみなので、これは適当な DP を行うことで O(N ^ 4) 程度で解くことができます。また、DP は畳み込みの形になっている上、dp[x][y][z] = (始状態のうち x 個が 1, 終状態のうち y 個が 1, 等しい箇所が z 個) は前計算のもと O(1) で求められるので、全体で O(HW \log HW \log H) で求めることもできます。