遗憾的是 math 里面一直没有很好的讲这个东西……所以这次细致说说。

FWT 的本质

类似于多项式卷积中，利用 ntt 变换使得卷积 $\to$ 点乘，fwt 也是类似的应用。

定义某种位运算 $\oplus$，那么 fwt 处理的位运算卷积形如：

$$H = F * G \implies H_k = \sum_{i \oplus j = k} F_i G_j $$

那么我们需要构造出一种变换，使得：

$$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 的考虑，分治：

$$fwt_i = \sum c(i, j) F_j = \sum_{j = 0}^{(n / 2) - 1} c(i, j) F_j + \sum_{j = n / 2}^{n - 1} c(i, j) F_j $$

将最高位拆出来，分别记为 $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;
			}
}