公式解説と全く同じ DP テーブルに対して別の説明を与えます。

列に対して、順に flip するかどうかを決める以下のような DP を考えます。

\(\mathrm{DP}[j][S][T][c]\) を以下の条件をともに満たすような \(x\) の個数(行の個数)と定めます。

• \(j<y\leq N\) のうち \(A_{x,y}=1\) となる \(y\) のなす集合が \(S\)
• 列 \(1,2,\ldots,j\) のうち flip する列の集合が \(T\) であるとき、\(1\leq y \leq j\) のうち flip を考慮したうえで \(A_{x,y}=1\) となる \(y\) の個数が \(c\)

\(\mathrm{DP}[j][*][*][*]\) から \(\mathrm{DP}[j+1][*][*][*]\) を配る DP により計算することを考えます。

• \(j+1\) 列目を flip するとき
  • \(\mathrm{DP}[j][S][T][c]\) からは
    \(\mathrm{DP}[j+1][S\setminus\{j+1\}][T\cup\{j+1\}][c+(j+1\in S?0:1)]\) に遷移する
• \(j+1\) 列目を flip しないとき
  • \(\mathrm{DP}[j][S][T][c]\) からは
    \(\mathrm{DP}[j+1][S\setminus\{j+1\}][T][c+(j+1\in S?1:0)]\) に遷移する

※ \((\mathrm{cond}?x:y)\) は「\(\mathrm{cond}\) が成り立つなら \(x\)、成り立たないなら \(y\) 」を表す略記

これらはともに定数時間で行えます。DP テーブルの状態数は \(W^2 2^W\) であることから、この DP は \(O(W^2 2^W)\) 時間で行えます。

この DP において、\(S\) と \(T\) はdisjoint であることから、\(S\cup T\) を1つにまとめることができ、それを整数にエンコードしたものを \(X\) とした DP テーブル \(\mathrm{DP}[X][j][c]\) は公式解説に登場するものと完全に一致します。