xor convolution - moririn2528’s blog

数列 A から数列 B を以下で生成

$b_k = \sum_{i \oplus j = k} a_i a_j$

( $\oplus$ は bitwise xor とする)

まず、数列 A を多項式

$f(x) = a_0 + a_1 x^1 + \dots + a_n x^n$

と表す。 $x^i \times x^j = x^{i \oplus j}$ となれば、FFT を用いて $O(n \log n)$ で計算可能。

ここで、 $bit(i,j)$ を $i$ の $j$ ビット目とし、

$x^i = \prod_j x_j^{bit(i,j)}$

とする。例を挙げると、 $x^3 = x_0^1 x_1^1$ 、 $x^5 = x_0^1 x_1^1 x_2^1$ となる。これは、xor がビットごとの計算である性質を表している。

次に、 $x_k^i \times x_k^j = x_k^{i \oplus j}$ と $x_k^i \times x_k^j = x_k^{(i+j) mod 2}$ は同値である。 $x_k^2 = 1$ 、つまり $x_k = -1, 1$ のとき、 $\times$ を乗算とすると上記の性質を持つようになり、 $x^i \times x^j = x^{i \oplus j}$ となる。これによって計算可能。実装は高速メビウス、ゼータ変換に似た形で可能。

参考

説明

Fast Walsh Hadamard Transforms and it's inner workings - Codeforces

実装

色々な畳み込み - kazuma8128’s blog