公式解説と同様に \(2\) 進数で考えます．\(x=0,1,\dots,2^W-1\) について以下を列挙できればよいです．

\[f(x)=\sum_{i=1}^{H}\min(\mathrm{popcount}(B_i\oplus x),W-\mathrm{popcount}(B_i\oplus x))\]

\(y=B_i\oplus x\iff x=y\oplus B_i\) なので以下のように表せます．

\[\begin{aligned} f(x) &=\sum_{\substack{0\leq y<2^W\\ 1\leq i\leq H\\ y\oplus B_i=x}}\min(\mathrm{popcount}(y),W-\mathrm{popcount}(y))\\ &=\sum_{\substack{0\leq y,z<2^W \\ y\oplus z=x}}g(y)h(z) \end{aligned}\]

ここで \(g,h\) は以下のように定めます．

• \(g(y)=\min(\mathrm{popcount}(y),W-\mathrm{popcount}(y))\)
• \(h(z)=\#\{i\mid 1\leq i\leq H,B_i=z\}\)

\(g\) は \(O(2^W)\) 時間，\(h\) は \(O(HW+2^W)\) 時間で計算でき， \(f\) は bitwise xor convolution によって \(O(W2^W)\) 時間で計算できます．