Xor Sum 4.5

$O(N^2)$ 解は非常に高速ですが、実行時間制限に間に合わせるのは非常に難しいと思われます。より高速な解法を考えます。

まず、 xor演算はbitごとに独立です。よって、$01$列 $A,B$ について、各操作回数 $k(0\leq k \leq N-1)$ に対する式の値を求めることが出来れば、その答えに適切に係数を掛けたものを足し合わせることにより元の問題を解くことが出来ます。 以下、$A,B$ は $01$ 列であり、0-indexedであるとします。

畳み込みを用いてこの問題を解くことを考えます。
多項式 $f(x),g(x)$ をそれぞれ以下のように定義します。

• $f(x)=a_0+a_1x+\ldots+a_{2N-1}x^{2N-1}$ 　$(A_{i \ mod \ N}=1$ ならば $a_i=1$、$A_{i \ mod \ N}=0$ ならば $a_i=-1)$
• $g(x)=b_0+b_1x+\ldots+b_{N-1}x^{N-1}$ 　$(B_{N-1-i}=1$ ならば $b_i=-1$、$B_{N-1-i}=0$ ならば $b_i=1)$

$f,g$ の畳み込みの結果を $h(x)$ とし、 $h$ の $x^k$ の係数を $C_k$ とすると、$N-(N-C_{2N-1-k})/2$ は $k$ 回操作を行ったときの式の値となります。

よって、各bitについてこの計算を行うことにより、 $O(N logN logA_{max})$ で元の問題を解くことが出来ました。($A_{max}$は $A_i,B_i$ の最大値)