遗憾的是 math 里面一直没有很好的讲这个东西……所以这次细致说说。
FWT 的本质
类似于多项式卷积中，利用 ntt 变换使得卷积 \(\to\) 点乘，fwt 也是类似的应用。
定义某种位运算 \(\oplus\)，那么 fwt 处理的位运算卷积形如：
那么我们需要构造出一种变换，使得：
\[H = F * G \iff fwt(H) = fwt(F) \cdot fwt(G) \]暂时我们还不得而知如何变换，考虑设 \(c(i, j)\) 表示变换系数，那么有：
\[fwt(F)_i = \sum c(i, j) F_j \]那么对应的点积：
\[fwt(H)_k = \sum_i \sum_j c(k, i) F_i c(k, j) G_j = \sum_i c(k, i) H_i \]根据卷积定义：
\[\sum_i c(k, i) H_i = \sum_i c(k, i) \sum_{x \oplus y = i} F_x G_y = \sum_x \sum_y F_x G_y c(k, x \oplus y) \]对比：
\[\sum_x \sum_y F_x G_y c(k, x \oplus y) = \sum_i \sum_j c(k, i) F_i c(k, j) G_j \]我们可以得知：
\[c(k, x \oplus y) = c(k, x) c(k, y) \]这个等式便是 fwt 的核心。
另外，考虑到位运算每一位是独立的，那么 \(c(x, y)\) 非常重要的性质是可以按位考虑。也就是说：
\[c(i, j) = c(i_0, j_0) c(i_1, j_1) \cdots \]其中 \(i_k\) 表示 \(i\) 的第 \(k\) 位。
那么我们只需要构造出 \(c(0/1, 0/1)\) 即可。
不妨假设我们已经构造出了 \(c\)，那么怎么求解呢？
类似 ntt 的考虑，分治：
将最高位拆出来，分别记为 \(i', j'\)：
\[fwt_i = c(i_0, 0) \sum_{j = 0}^{(n / 2) - 1} c(i, j) F_j + c(i_0, 1) \sum_{j = n / 2}^{n - 1} c(i, j) F_j \]于是分半之后：
\[fwt(F)_i = c(i_0, 0) fwt(F_0)_i + c(i_0, 1) fwt(F_1)_i \]于是可以 \(O(n)\) 的合并两个规模减半的东西了，于是总复杂度 \(O(w 2^w)\)，其中 \(w\) 是位数。
对于逆变换，将 \(c\) 求个逆，变换回去即可。
FWT 的构造
现在我们对于 \(\texttt{or, and, xor}\) 尝试构造其 \(c\) 矩阵。
\(\texttt{or}\)
首先，注意到 \(c(0, 0) c(0, 0) = c(0, 0 | 0)\)，于是 \(c(0, 0) = 0/1\)。
同理，不难得出 \(c(0/1, 0/1) \in \{0, 1\}\)。
考虑 \(c(0, 0) c(0, 1) = c(0, 1)\) 可以得出 \(c(0, 0) = c(0, 1) = 1\) 或者 \(c(0, 1) = 0\)。
同理考虑 \(c(1, 0) c(1, 1) = c(1, 1)\) 也可以知道 \(c(1, 1) = 0\) 或者 \(c(1, 0) = c(1, 1) = 1\)。
注意到需要构造出的矩阵有逆，那么只能是：
\[\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \text{或者} \begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix} \]值得注意的是，第二种矩阵 \(c(i, j)\) 对应的等式为 \([i \& j = j]\)，也就是说：
\[fwt_i = \sum_{i \& j = j} F_j = \sum_{j \subseteq i} F_j \]相当于子集求和！
void fwtor(int n, int inv = {1, -1}) {
for (int u = 2, k = 1; u <= n; u <<= 1, k <<= 1)
for (int i = 0; i < n; i += u)
for (int j = 0; j < k; ++j)
fwt[i + j + k] += fwt[i + j] * inv;
}
\(\texttt{and}\)
首先还是注意到 \(c(0/1, 0/1) \in \{0, 1\}\)。
考虑 \(c(0, 0) c(0, 1) = c(0, 0)\) 得出 \(c(0, 0) = 0\) 或者 \(c(0, 0) = c(0, 1) = 1\)。
同理考虑 \(c(1, 0) c(1, 1) = c(1, 0)\) 得出 \(c(1, 0) = 0\) 或者 \(c(1, 0) = c(1, 1) = 1\)。
那么还是：
\[\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix} \text{或者} \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix} \]值得注意的是，第一种矩阵 \(c(i, j)\) 对应的是 \([i \& j = i]\)，也就是说：
\[fwt_i = \sum_{i \& j = j} F_j = \sum_{i \subseteq j} F_j \]相当于超集求和！
void fwtand(int n, int inv = {1, -1}) {
for (int u = 2, k = 1; u <= n; u <<= 1, k <<= 1)
for (int i = 0; i < n; i += u)
for (int j = 0; j < k; ++j)
fwt[i + j] += fwt[i + j + k] * inv;
}
\(\texttt{xor}\)
考虑对于任意 \(x, y \in \{0, 1\}\) 存在 \(c(0, 0) c(x, y) = c(x, y)\)，那么一定存在 \(c(0, 0) = 1\)，否则 \(c(1, 1) = c(1, 0) = 0\) 显然没有逆，不可行。
考虑 \(c(0, 1) c(0, 1) = c(0, 0)\)，那么 \(c(0, 1) = \pm 1\)。
\(c(1, 0) c(1, 0) = c(1, 1) c(1, 1) = c(1, 0)\)，所以 \(c(1, 0) = 1\)，否则 \(c(1, 1) = c(1, 0) = 0\) 则显然没有逆。
\(c(1, 1) c(1, 1) = c(1, 0)\)，考虑到 \(c(1, 0) = 1\)，那么自然 \(c(1, 1) = \pm 1\)。
所以可行的矩阵为：
\[\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} \text{或者} \begin{bmatrix} 1 & -1 \\ 1 & 1 \end{bmatrix} \]注意到对于第一个矩阵，实际上的系数为 \((-1)^{|i \& j|}\)。啥也不相当于。
void fwtxor(int n, int inv = {1, 1/2}) {
for (int u = 2, k = 1; u <= n; u <<= 1, k <<= 1)
for (int i = 0; i < n; i += u)
for (int j = 0; j < k; ++j) {
int x = fwt[i + j], y = fwt[i + j + k];
fwt[i + j] = (x + y) * inv, fwt[i + j + k] = (x - y) * inv;
}
}