一、快速沃尔什变换-简介

我们知道，FFT（快速傅里叶变换）用于解决一类形如 $C_k = \sum\limits _{i+j=k} A_i \times B_j$ 的问题。
至于形如 $C_k = \sum\limits _{i \oplus j=k} A_i \times B_j$ 的问题，我们称其为位运算卷积，可以用 FWT（快速沃尔什变换）在 $O(n \log n)$ 的时间复杂度内解决。

快速沃尔什变换 与 快速傅里叶变换 解决的问题很像，思路也大致相同。
总体思路：先对多项式正变换，再按位相乘，再逆变换。

二、一些约定

这里先约定如下运算：
$A+B$ 表示多项式按位相加。
$A-B$ 表示多项式按位相减。
$A*B$ 表示多项式按位相乘。
$(A,B)$ 表示 $A$ 和 $B$ 直接拼接。

三、或运算卷积

$$\large C_k = \sum\limits _{i | j=k} A_i \times B_j$$

显然对于或运算，有如下性质：$j|i=i,k|i=i \rightarrow (j|k)|i=i$。
因此我们构造 $FWT(A)_i=\sum_{j|i=i} A_j$。

于是：

$$ \begin{aligned} FWT(A) \times FWT(B) &= (\sum_{j|i=i} A_i) \times (\sum_{k|i=i} B_i)\\ &=\sum_{j|i=i}\sum_{k|i=i} A_j \times B_k\\ &=\sum_{(j|k)|i=i} A_j \times B_k\\ &=FWT(C)\\ \end{aligned} $$

正变换：$A \rightarrow FWT(A)$

我们约定 $A$ 的长度为 $2^n$，设 $A_0$ 表示前 $2^{n-1}$ 项，$A_1$ 表示后 $2^{n-1}$ 项。

性质 1

$FWT(A) + FWT(B) = FWT(A + B)$

证明：

$FWT(A)_i=\sum_{j|i=i} A_j$
$FWT(B)_i=\sum_{j|i=i} B_j$
$FWT(A + B)_i = \sum_{j|i=i} A_j + B_j = \sum_{j|i=i} A_j + \sum_{j|i=i} B_j = FWT(A) + FWT(B)$

$FWT(A)=\left\{ \begin{aligned} & (FWT(A_0, FWT(A_0)+FWT(A_1)) & (n > 0) \\ & A & (n > 0) \\ \end{aligned} \right. $

证明（含解析）：

FWT 和 FFT 非常类似，所以考虑同样用分治解决，把 $A$ 分为 $A_0$ 和 $A_1$。
FWT 的定义式中，相当于是一个枚举子集的过程。

• 观察到 $A_0$ 中每一位下标的最高位一定是 $0$，所以它的子集只能是它自己，即 $FWT(A_0)$。
• 而 $A_1$ 最高位是 $1$，所以它要包含它自己和 $A_0$，即 $FWT(A_0) + FWT(A_1)$。

于是就可以直接进行正变换了。

关于求解的证明

为什么正变换之后直接按位乘就可以了？

$$ \begin{aligned} FWT(C)_i &= \sum_{j \in i} C_j\\ &=\sum_{j \in i}\sum_{x|y=j} A_x \times B_y\\ &=\sum_{(x|y) \in i} A_x \times B_y\\ &=\sum_{x \in i} A_x \times \sum_{y \in i} B_y\\ &=FWT(A)_i \times FWT(B)_i \\ \end{aligned} $$

于是我们已经完成了正变换 $A \rightarrow FWT(A)$ 和求解 $FWT(C)$，接下来就是逆变换 $FWT(C) \rightarrow C$。

逆变换：$FWT(A) \rightarrow A$

这里将逆变换称为 $IFWT$，满足 $A=IFWT(FWT(A))$。
上次经过变换前的是 $A$，这次变换前的就是 $FWT(A)$，所以这次我们把 $FWT(A)$ 分成 $FWT(A)_0$ 和 $FWT(A)_1$。
其实逆变换只要反着做就行了。

显然，$A_0$ 只由 $FWT(A)_0$ 变换得到。
而 $A_1$ 由 $FWT(A)_1 - FWT(A)_0$ 得到，因为 $FWT(A)_1$ 包含了下标在二进制下最高位分别为 $0$ 和 $1$ 的状态，而我们只要 $1$，所以要扣掉多余的贡献。

即 $IFWT(A) = (IFWT(A_0), IFWT(A_1) - IFWT(A_0))$
这里的 $A$ 实际上代表 $FWT(A)$，即正变换后的结果，这里写成了一般式而已。

或运算卷积-代码

如下代码将对 $a$ 数组进行变换，为了使代码更加简洁，$op$ 的正负性表示正变换或逆变换，因为它们本质相同，只是正负号改变。

void Or(int *a, int op) {
    for (int len = 1; len < (1 << n); len <<= 1) {  //枚举分治长度
        for (int i = 0; i < (1 << n); i += (len << 1)) {
            for (int j = 0; j < len; j++) a[i + j + len] += a[i + j] * op;
        }
    }
}

四、与运算卷积

$$\large C_k = \sum\limits _{i \& j=k} A_i \times B_j$$

由于是与运算，所以这里重新定义 $FWT(A)_i=\sum_{j|i=j} A_j$，即 $i$ 是 $j$ 的子集。

性质 1

$FWT(A) + FWT(B) = FWT(A + B)$

证明：

与或运算大致相同。

正变换 $A \rightarrow FWT(A)$

$FWT(A)=\left\{ \begin{aligned} & (FWT(FWT(A_0)+FWT(A_1), A_1) & (n > 0) \\ & A & (n > 0) \\ \end{aligned} \right. $

证明（含解析）：

• 同理，$A_0$ 中每一位下标的最高位一定是 $0$，最高位 $0 \& 1 = 0$，所以 $FWT(A_1)$ 也要加上贡献，即 $FWT(A_0) + FWT(A_1)$。
• $A_1$ 最高位是 $1$，所以它只有它自己的子集，即 $FWT(A_1)$。

关于求解的证明

与 或运算卷积 是很类似的。
注意下标的不同。

$$ \begin{aligned} FWT(C)_i &= \sum_{i \in j} C_j \\ &=\sum_{i \in j}\sum_{x|y=j} A_x \times B_y \\ &=\sum_{i \in (x|y)} A_x \times B_y \\ &=\sum_{i \in x} A_x \times \sum_{i \in y} B_y \\ &=FWT(A)_i \times FWT(B)_i \\ \end{aligned} $$

逆变换：$FWT(A) \rightarrow A$

这次仍然把 $FWT(A)$ 分成 $FWT(A)_0$ 和 $FWT(A)_1$，还是反着做。

$A_0$ 由 $FWT(A)_0 - FWT(A)_1$ 得到，因为 $FWT(A)_0$ 包含了下标在二进制下与运算最高位分别为 $0$ 和 $1$ 的状态，而我们只要 $0$，所以要扣掉多余的贡献。
$A_1$ 就只能从子集转移而来了。

即 $IFWT(A) = (IFWT(A_0) - IFWT(A_1), IFWT(A_1))$
这里的 $A$ 实际上代表 $FWT(A)$，即正变换后的结果，这里写成了一般式而已。

与运算卷积-代码

如下代码将对 $a$ 数组进行变换，为了使代码更加简洁，$op$ 的正负性表示正变换或逆变换，因为它们本质相同，只是正负号改变。

void And(int *a, int op) {
    for (int len = 1; len < (1 << n); len <<= 1) {  //枚举分治长度
        for (int i = 0; i < (1 << n); i += (len << 1)) {
            for (int j = 0; j < len; j++) a[i + j] += a[i + j + len] * op;
        }
    }
}

五、异或运算卷积

$$\large C_k = \sum\limits _{i \Lambda j=k} A_i \times B_j$$

这里用一个比较玄学的定义方式：$FWT(A)_i=\sum\limits_{j=0}^{2^n-1} (-1)^{c(i \& j)} A_j$。
其中 $c(i)$ 表示 $i$ 二进制下 $1$ 的个数。
并约定 $\Lambda$ 为异或。

性质 1

$FWT(A)_i = \Big( \sum\limits_{c(i \& j) \bmod 2 = 0} A_j \Big) - \Big( \sum\limits_{c(i \& j) \bmod 2 = 1} A_j \Big)$

证明：

无非就是奇偶性拆开罢了。

正变换 $A \rightarrow FWT(A)$

$FWT(A)=\left\{ \begin{aligned} & (FWT(A_0)+FWT(A_1),FWT(A_0)-FWT(A_1)) & (n > 0) \\ & A & (n > 0) \\ \end{aligned} \right. $

证明：

$$ \begin{aligned} FWT(A) FWT(B) &= \Big( \sum\limits_{c(i \& j) \bmod 2 = 0} A_j \Big) - \Big( \sum\limits_{c(i \& j) \bmod 2 = 1} A_j \Big) \times \Big( \sum\limits_{c(i \& k) \bmod 2 = 0} B_k \Big) - \Big( \sum\limits_{c(i \& k) \bmod 2 = 1} B_k \Big) \\ &= \sum\limits_{c(i \& j) \Lambda c(i \& k) = 0} A_j B_k - \sum\limits_{c(i \& j) \Lambda c(i \& k) = 1} A_j B_k \\ &= \sum\limits_{c(i \& (j \Lambda k) = 0} A_j B_k - \sum\limits_{c(i \& (j \Lambda k) = 1} A_j B_k \\ &= FWT(C) \end{aligned} $$

得到：$$FWT(A) = (FWT(A_0)+FWT(A_1),FWT(A_0)-FWT(A_1))$$

逆变换：$FWT(A) \rightarrow A$

$$IFWT(A)=(\frac{IFWT(A_0)+IFWT(A_1)}{2}, \frac{IFWT(A_0)-IFWT(A_1)}{2})$$

异或运算卷积-代码

如下代码将对 $a$ 数组进行变换，为了使代码更加简洁，$op$ 为 $1$ 表示正变换，为 $\frac{1}{2}$ 表示逆变换，因为它们本质相同，只是正负号改变。

void Xor(int *a, int op) {
    for (int len = 1; len < (1 << n); len <<= 1) {  //枚举分治长度
        for (int i = 0; i < (1 << n); i += (len << 1)) {
            for (int j = 0; j < len; j++) {
                a[i + j] = (a[i + j] + a[i + j + len]) * op, a[i + j + len] = (a[i + j] - a[i + j + len]) * op;
            }
        }
    }
}