快速沃尔什变换（FWT）
前言
本文为个人学习笔记，大量参考了 oi-wiki 以及其他博客的内容。
问题
给定 \(a, b\) 序列，求：
\[c_i = \sum_{i = j \oplus k} a_j b_k \]其中，\(\oplus = \operatorname{or} / \operatorname{and} / \operatorname{xor}\)。
做法
核心思想
对于某种特定的 \(\oplus\)，找到序列 \(FWT_a, FWT_b, FWT_c\) 分别对应序列 \(a, b, c\)，需要满足以下性质和要求：
1、\(FWT_{c_i} = FWT_{a_i} \cdot FWT_{b_i}\)；
2、需要在优秀的时间复杂度内进行 \(a\) 和 \(FWT_a\) 的变换。
下面一个一个符号来。
\(\operatorname{or}\)
\[FWT_{a_i} = \sum_{j, j | i = i} a_j \\ FWT_{a_i} \cdot FWT_{b_i} = \sum_{j, j | i = i} a_j \cdot \sum_{k, k | i = i} b_j = \sum_{j, k, (j | k) | i = i} (a_jb_k) = FWT_{c_i} \]考虑 \(a\) 和 \(FWT_a\) 的变换，考虑分治处理，写出如下形式（\(a_0, a_1, a_2, a_3, a_4, a_5, a_6, a_7\)）：
| 轮数 | 长度 | \(FWT_0\) | \(FWT_1\) | \(FWT_2\) | \(FWT_3\) | \(FWT_4\) | \(FWT_5\) | \(FWT_6\) | \(FWT_7\) |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | \(a_0\) | \(a_1\) | \(a_2\) | \(a_3\) | \(a_4\) | \(a_5\) | \(a_6\) | \(a_7\) |
| 2 | 2 | \(a_0\) | \(a_0 + a_1\) | \(a_2\) | \(a_2 + a_3\) | \(a_4\) | \(a_4 + a_5\) | \(a_6\) | \(a_6 + a_7\) |
| 3 | 4 | \(a_0\) | \(a_0 + a_1\) | \(a_0 + a_2\) | \(a_0 + a_1 + a_2 + a_3\) | \(a_4\) | \(a_4 + a_5\) | \(a_4 + a_6\) | \(a_4 + a_5 + a_6 + a_7\) |
| 4 | 8 | \(a_0\) | \(a_0 + a_1\) | \(a_0 + a_2\) | \(a_0 + a_1 + a_2 + a_3\) | \(a_0 + a_4\) | \(a_0 + a_1 + a_4 + a_5\) | \(a_0 + a_2 + a_4 + a_6\) | \(a_0 + a_1 + a_2 + a_3 + \\ a_4 + a_5 + a_6 + a_7\) |
容易写出以下代码，
inline void FWT_OR(int *A) {
for (int len = 2; len <= (1 << n); len *= 2)
for (int x = 0; x < (1 << n); x += len)
for (int i = x; i < x + len / 2; ++ i)
A[i + len / 2] = (A[i] + A[i + len / 2]) % mod;
}
对于 \(FWT_a\) 变换为 \(a\)，反着把 \(FWT_a\) 数组转化为 \(a\) 数组即可。
inline void IFWT_OR(int *A) {
for (int len = (1 << n); len >= 2; len /= 2)
for (int x = 0; x < (1 << n); x += len)
for (int i = x; i < x + len / 2; ++ i)
A[i + len / 2] = (A[i + len / 2] - A[i]) % mod;
}
\(\operatorname{and}\)
\[FWT_{a_i} = \sum_{j, j \& i = i} a_j \\ FWT_{a_i} \cdot FWT_{b_i} = \sum_{j, j \& i = i} a_j \cdot \sum_{k, k \& i = i} b_j = \sum_{j, k, (j \& k) \& i = i} (a_jb_k) = FWT_{c_i} \]\(FWT_a\) 和 \(a\) 的变换同上。
inline void FWT_AND(int *A) {
for (int len = 2; len <= (1 << n); len *= 2)
for (int x = 0; x < (1 << n); x += len)
for (int i = x; i < x + len / 2; ++ i)
A[i] = (A[i] + A[i + len / 2]) % mod;
}
inline void IFWT_AND(int *A) {
for (int len = (1 << n); len >= 2; len /= 2)
for (int x = 0; x < (1 << n); x += len)
for (int i = x; i < x + len / 2; ++ i)
A[i] = (A[i] - A[i + len / 2]) % mod;
}
\(\operatorname{xor}\)
这个比较难。
以下摘自 oi-wiki。
若我们令 \(x\circ y\) 表示 \(x\cap y\) 中 1 数量的奇偶性，即 \(x\circ y=\text{popcnt}(x\cap y)\bmod 2\)，那么容易有 \((x\circ y)\operatorname{xor} (x\circ z)=x\circ(y\operatorname{xor} z)\)。
下证上式（\((x\circ y)\operatorname{xor} (x\circ z)=x\circ(y\operatorname{xor} z)\)）：
只考虑 \(x\) 的二进制中为 1 的位，\(x\cap y\) 中 1 的数量 和 \(x\cap z\) 中 1 的数量可以分成三个部分：
1、都有的数量 \(A\)
2、仅有 \(y\) 有的数量 \(B\)
3、仅有 \(z\) 有的数量 \(C\)
即证明：\(((A + B) \bmod 2) \operatorname {xor} ((A + C) \bmod 2)= (B + C) \bmod 2\)
显然，当 \(A = B = C = 0\) 时上式成立，\(A\)，\(B\)，\(C\) 增加 1 并不会改变上述等式。
\(FWT[A]_i=\sum_{i\circ j=0}A_j-\sum_{i\circ j=1}A_j\)，证明如下：
\[\begin{aligned} FWT[A]_iFWT[B]_i&=\left(\sum_{i\circ j=0}A_j-\sum_{i\circ j=1}A_j\right)\left(\sum_{i\circ k=0}B_k-\sum_{i\circ k=1}B_k\right) \\ &=\left(\sum_{i\circ j=0}A_j\sum_{i\circ k=0}B_k+\sum_{i\circ j=1}A_j\sum_{i\circ k=1}B_k\right)-\left(\sum_{i\circ j=0}A_j\sum_{i\circ k=1}B_k+\sum_{i\circ j=1}A_j\sum_{i\circ k=0}B_k\right) \\ &=\sum_{(j\oplus k)\circ i=0}A_jB_k-\sum_{(j\oplus k)\circ i=1}A_jB_k \\ &=FWT[C]_i \end{aligned} \]inline void FWT_XOR(int *A) {
for (int len = 2; len <= (1 << n); len *= 2)
for (int x = 0; x < (1 << n); x += len)
for (int i = x; i < x + len / 2; ++ i) {
A[i] = (A[i] + A[i + len / 2]) % mod;
A[i + len / 2] = (A[i] - 2 * A[i + len / 2]) % mod;
}
}
inline void IFWT_XOR(int *A) {
for (int len = (1 << n); len >= 2; len /= 2)
for (int x = 0; x < (1 << n); x += len)
for (int i = x; i < x + len / 2; ++ i) {
A[i + len / 2] = 1ll * (A[i] - A[i + len / 2])
* quick_pow(2, mod - 2) % mod;
A[i] = (A[i] - A[i + len / 2]) % mod;
}
}
同或
若我们令 \(x\circ y\) 表示 \(x\cup y\) 中 1 数量的奇偶性，即 \(x\circ y=\text{popcnt}(x\cup y)\bmod 2\)。
\(FWT[A]_i=\sum_{i\circ j=0}A_j-\sum_{i\circ j=1}A_j\)。
标签：circ,变换,sum,len,int,沃尔什,FWT,operatorname From： https://www.cnblogs.com/chzhc-/p/18530960