概念

两个多项式的乘法卷积为：

$$(F*G)(x)=\sum_{i=j\times k}F_j\cdot G_k $$

现在我们考虑探究逻辑与、或、异或的卷积，即：

$$(F*G)(x)=\sum_{i=j\odot k}F_j\cdot G_k $$

其中 $\odot$ 可以代表与、或、异或二元位运算。若 $\odot$ 为逻辑与、或，为优化这样卷积而进行的变换被叫做快速莫比乌斯变换（Fast Möbius Transform）；若 $\odot$ 为逻辑异或，为优化卷积而进行的变换被叫做快速沃尔什变换（Fast Walsh Transform）。有时也用 FWT 统称 FMT 和 FWT，以下就用沃尔什变换统称二者。

FWT 与 FFT 的过程类似，先用 $\mathcal{O}(n\log n)$ 的时间把多项式变换，用 $\mathcal{O}(n)$ 的时间完成卷积，再用 $\mathcal{O}(n\log n)$ 的时间把多项式变换回来。

但由于位运算与乘法有区别，所以 FWT 不是变换到点值表示，它的变换内容还要分别考虑。

构造变换

要构造三种位运算的变换过程都相近。

即考虑构造变换 $T$ ，使得 $T(F)_i\cdot T(G)_i=T(F\ast G)_i$ 。如此构造就能在 $\mathcal{O}(n)$ 时间完成卷积。

逻辑或

要求

$$(F\ast G)(x)=\sum_{i=j\vee k}F_j\cdot G_k $$

显然有 $j\vee i=i,k\vee i=i\Rightarrow (j\vee k)\vee i=i$ 。

构造 $T_{\mathrm{or}}(A)_i=\sum_{j\vee i=i}A_j$ 。

则有：

$$\begin{aligned} T_{\mathrm{or}}(F)_i\cdot T_{\mathrm{or}}(G)_i&=\left(\sum_{j\vee i=i}F_j\right)\left(\sum_{k\vee i=i}G_k\right)\\ &=\sum_{j\vee i=i}\sum_{k\vee i=i}F_j\cdot G_k\\ &=\sum_{(j\vee k)\vee i=i}F_j\cdot G_k\\ &=T_{\mathrm{or}}(F\ast G)_i \end{aligned}$$

逻辑与

逻辑与同理， $T_{\mathrm{and}}(A)_i=\sum_{j\wedge i=i}A_j$ 。

逻辑异或

异或的性质相较于上两者更复杂。

定义运算 $a\otimes b=\mathrm{popcount}(a\wedge b)\bmod2$ ，其中 $\mathrm{popcount}(x)$ 表示 $x$ 在二进制下 $1$ 的个数。

满足 $(i\otimes j)\oplus(i\otimes k)=i\otimes(j\oplus k)$ ，其中 $\oplus$ 表示异或。

构造 $T_{\mathrm{xor}}(A)_i=\sum_{i\otimes j=0}A_j-\sum_{i\otimes j=1}A_j$ 。

则有：

$$\begin{aligned} T_{\mathrm{xor}}(F)_i\cdot T_{\mathrm{xor}}(G)_i&=\left(\sum_{i\otimes j=0}F_j-\sum_{i\otimes j=1}F_j\right)\left(\sum_{i\otimes k=0}G_k-\sum_{i\otimes k=1}G_k\right)\\ &=\left(\sum_{i\otimes j=0}F_j\right)\left(\sum_{i\otimes k=0}G_k\right)-\left(\sum_{i\otimes j=0}F_j\right)\left(\sum_{i\otimes k=1}G_k\right)-\left(\sum_{i\otimes j=1}F_j\right)\left(\sum_{i\otimes k=0}G_k\right)+\left(\sum_{i\otimes j=1}F_j\right)\left(\sum_{i\otimes k=1}G_k\right)\\ &=\sum_{i\otimes(j\oplus k)=0}F_j\cdot G_k-\sum_{i\otimes(j\oplus k)=1}F_j\cdot G_k\\ &=T_{\mathrm{xor}}(F*G)_i \end{aligned}$$

变换

要 $\mathcal{O}(n\log n)$ 变换，考虑对多项式进行分治。对于一个最高次项是 $2n$ 的多项式 $A$ ，我们把它分成两部分 $A_0,A_1$ 讨论，分别表示前 $2^{n−1}$ 次项和后面的 $2n−1$ 次项。

或

对于或卷积有：

$$T_{\mathrm{or}}(A)=\mathrm{merge}\left(T_{\mathrm{or}}(A_0),T_{\mathrm{or}}(A_0)+T_{\mathrm{or}}(A_1)\right) $$

其中 $\mathrm{merge}(A,B)$ 表示将 $A,B$ 两个多项式合并。

对于逆变换，可根据正变换的式子得：

$$A=\mathrm{merge}(A_0,A_1-A_0) $$

与

与同理。

异或

对于异或卷积有：

$$T_{\mathrm{xor}}(A)=\mathrm{merge}(T_{\mathrm{xor}}(A_0)+T_{\mathrm{xor}}(A_1),T_{\mathrm{xor}}(A_0)-T_{\mathrm{xor}}(A_1)) $$

同理逆变换有：

$$A=\mathrm{merge}\left(\dfrac{A_0+A_1}{2},\dfrac{A_0-A_1}{2}\right) $$

代码

代码合并了 FWT 和 IFWT。

void OR(int *f, int op = 1) {  // IFWT  op=-1
    for (int k = 1; k < n; k <<= 1)
        for (int i = 0; i < n; i += (k << 1))
            for (int j = 0; j < k; j++)
                (f[i + j + k] += f[i + j] * op % mod) %= mod;
}

void AND(int *f, int op = 1) {   // IFWT  op=-1
    for (int k = 1; k < n; k <<= 1)
        for (int i = 0; i < n; i += (k << 1))
            for (int j = 0; j < k; j++)
                (f[i + j] += f[i + j + k] * op % mod) %= mod;
}

void XOR(int *f, int op = 1) {   // IFWT  op=1/2
    for (int k = 1; k < n; k <<= 1)
        for (int i = 0; i < n; i += (k << 1))
            for (int j = 0; j < k; j++) {
            	int x = f[i + j], y = f[i + j + k];
                f[i + j] = (x + y) %= mod;
                f[i + j + k] = (x - y + mod) %= mod;
                (f[i + j] *= op) %= mod, (f[i + j + k] *= op) %= mod;
            }
}