快速沃尔什变换

快速沃尔什变换，简称 FWT 。

用处

多项式卷积一般是这样的：

\[ C_i = \sum_{j + k = i} A_j \cdot B_k \]

这个可以用 FFT 快速求解。

然而还有一个诡异的卷积：

\[ C_i = \sum_{j \oplus k = i} A_j \cdot B_k \]

其中 $ $ 是任意一种位运算。

FWT 便是求这类卷积的快速算法。

构造

FFT 的思想是把多项式转换成可以线性相乘的点值表示法 (DFT) ，
再把相乘的结果转换回系数表示法 (IDFT) 。

同样的道理可以用在 FWT 上，用 DWT 将多项式转换成可以线性相乘的形式，即：

\[ DWT(C)_i = DWT(A)_i \cdot DWT(B)_i \]

再用 IDWT 将相乘的结果转换回来。

DWT

目标是构造一个转移系数函数 f(i, j) ，满足：

\[ DWT(A)_i = \sum_j A_j \cdot f(i, j) \]

考虑 f(i, j) 应满足什么样的性质。

首先根据 DWT 的性质：

\[ DWT(C)_i = DWT(A)_i \cdot DWT(B)_i \]

\[ \sum_t C_t f(i, t) = \sum_j A_j f(i, j) \sum_k B_k f(i, k) \]

\[ \sum_t \sum_{j \oplus k = t} A_j B_k f(i, t) = \sum_j \sum_k A_j f(i, j) B_k f(i, k) \]

\[ \sum_t \sum_{j \oplus k = t} A_j B_k f(i, t) = \sum_t \sum_{j \oplus k = t} A_j f(i, j) B_k f(i, k) \]

由上式可得出：

\[ \forall i, j, k: f(i, j) f(i, k) = f(i, j \oplus k) \]

这样还不够，为了让 DWT 快速进行，f(i, j) 还应满足以下性质：

\[ f(i, j) = \prod_k f(i_k, j_k) \]

其中 $ i_k $ 表示 i 二进制下的第 k 位（ 0 或 1 ）。

有了这个性质，就可已通过 f(0, 0), f(0, 1), f(1, 0), f(1, 1) 的值相乘得出所有 f 。
有了这个性质，就可以考虑分治求 DWT ：

\[DWT(A)_i = \sum_{j=0}^{n-1} A_j f(i, j)\]

\[ = \sum_{j=0}^{n/2-1} A_j f(i, j) + \sum_{j=n/2}^{n-1} A_j f(i, j) \]

\[ = \sum_{j=0}^{n/2-1} A_j \prod_k f(i_k, j_k) + \sum_{j=n/2}^{n-1} A_j \prod_k f(i_k, j_k) \]

\[ = \sum_{j=0}^{n/2-1} f(i_0, j_0) A_j \prod_{k \geq 1} f(i_k, j_k) + \sum_{j=n/2}^{n-1} A_j f(i_0, j_0) \prod_{k \geq 1} f(i_k, j_k)\]

\[ = f(i_0, 0) \sum_{j=0}^{n/2-1} A_j \prod_k f(i_k, j_k) + f(i_0, 1) \sum_{j=n/2}^{n-1} A_j \prod_k f(i_k, j_k) \]

规模减小了一半，递归或迭代地分治下去。
每次将 A 分成左右两半 A0, A1 ：

\[ DWT(A)_i = f(0, 0) DWT(A0)_i + f(0, 1) DWT(A1)_i , i < n / 2 \]

\[ DWT(A)_i = f(1, 0) DWT(A0)_i + f(1, 1) DWT(A1)_i , i \geq n / 2 \]

想到 FFT 的蝴蝶变换没有？ 答：没有
迭代的 DWT 这里也有类似的蝴蝶变换：

int x = A[i], y = A[i + k];
A[i] = f00 * x + f01 * y;
A[i + k] = f10 * x + f11 * y;

DWT 的过程就是这样了，甚至不需要构造整个 f ，
只需要 f(0, 0), f(0, 1), f(1, 0), f(1, 1) 即可，
需要满足的就是 $ i, j, k: f(i, j) f(i, k) = f(i, j k) $ 。

IDWT

怎么将 DWT 的结果转换回来？ 观察 DWT 的蝴蝶变换：

a = f00 * x + f01 * y;
b = f10 * x + f11 * y;

DWT 通过 x, y 求出 a, b,
IDWT 就是通过 a, b 求 x, y 。

解二元一次方程就好了：
x = (f11 * a - f01 * b) / (f00 * f11 - f01 * f10)
y = (f10 * a - f00 * b) / (f01 * f10 - f00 * f11)

就是这么简单...

个屁啊。

考虑 f 的构造，
要满足 DWT 的性质把所有的 f 设为 0 不就可以了？
要满足 DWT 的性质把所有的 f 设为 1 不就可以了？

这样且不是对于任何位运算都会有相同的结果？

Naive.

再看看 IDWT ，分母里边是不是有 (f01 * f11 - f01 * f10) ？
不幸的是把 f 全部设为 0 或者全设为 1 这个分母都是 0 ，
这意味着 IDWT 的二元一次方程无解，转过去就转不回来了。

因此 f 的构造还要满足一个条件： f01 * f11 != f01 * f10 。

f 的构造

f 需要满足的性质已经讲的很详细了。

这里给出常用位运算中 f 的构造：

• 按位或： f00 = 1, f01 = 0, f10 = 1, f11 = 1
• 按位与： f00 = 1, f01 = 1, f10 = 0, f11 = 1
• 异或： f00 = 1, f01 = 1, f10 = 1, f11 = -1

可以自行验证，这些 f 满足上述性质。

实际意义

一个多项式 A DFT 后的 \(A2_x\) 实际意义就是 A 在 $ W_n^x $ 上的值（点值表示）。

那么 A DWT 后的结果的现实意义呢？
这得分类来说。

按位或

A 在做按位或的 DWT 之后得到的 A2 满足： \[ A2_x = \sum_{i|x=x} A_i \]

也就是说 \(A2_x\) 表示 x 的每个子集 i 的 \(A_i\) 的和。
不难得到，\(A2_x \cdot B2_x\) 的结果 \(C2_x\) 就是 A, B 卷积后的 C 的变换： \[ A2_x \cdot B2_x = \sum_{i|x=x} A_i \sum_{j|x=x} B_j \] \[ A2_x \cdot B2_x = \sum_{i|x=x} \sum_{j|x=x} A_i B_j \] \[ A2_x \cdot B2_x = \sum_{k|x=x} \sum_{i|j=k} A_i B_j \] \[ A2_x \cdot B2_x = \sum_{k|x=x} C_k \] \[ A2_x \cdot B2_x = C2_x \]

事实上，这也就是子集和变换 FMT （快速莫比乌斯变换） 。

感性理解一下

按位与

和按位或类似的，A 在做按位与的 DWT 之后得到的 A2 满足： \[ A2_x = \sum_{i\&x=x} A_i \]

也就是说 \(A2_x\) 表示每个包含 x 的集合 i 的 \(A_i\) 的和。
不难得到，\(A2_x \cdot B2_x\) 的结果 \(C2_x\) 就是 A, B 卷积后的 C 的变换： \[ A2_x \cdot B2_x = \sum_{i\&x=x} A_i \sum_{j\&x=x} B_j \] \[ A2_x \cdot B2_x = \sum_{i\&x=x} \sum_{j\&x=x} A_i B_j \] \[ A2_x \cdot B2_x = \sum_{k\&x=x} \sum_{i\&j=k} A_i B_j \] \[ A2_x \cdot B2_x = \sum_{k\&x=x} C_k \] \[ A2_x \cdot B2_x = C2_x \]

和按位或一个模子里刻出来的

子集卷积

两个多项式 A, B 的子集卷积 C 的意义如下：

\[ C(x) = \sum_{y|z=x, y\&z=0} A(y) B(z) \]

也就是把 x 划分为两个子集 y, z 的 A(y) * B(z) 的和。

转换成 $ {y|z=x} A(y) B(z) [y & z = 0] $ ，似乎是一个按位或卷积。
再转换成 $ {y|z=x} A(y) B(z) [bitcount(y) + bitcount(z) = bitcount(x)] $ 。

此时需要考虑的就是 bitcount, 也就是集合大小，也就是二进制位中 1 的个数。
集合大小是 $ O(log(n)) $ 的，可以考虑枚举大小，设： \[ A_i(x) = A(x) [bitcount(x) = i] \] \[ B_j(x) = B(x) [bitcount(x) = j] \] \[ C_k(x) = C(x) [bitcount(x) = k] \]

那么有： \[ C_k(x) = \sum_{y|z=x} A_i(y) B_j(z) [i + j = k] \] \[ C_k(x) = \sum_{i+j=k} \sum_{y|z=x} A_i(y) B_j(z) \]

那么枚举 i, j 的值，将 $ A_i $ 和 $ B_j $ 卷积后贡献到 $ C_{i+j} $ 即可。

这样复杂度似乎是 $ O(n log^3n) $ 的，
但是事实上每个 $ A_i, B_j $ 都可以提前 FWT 后 $ O(n) $ 相乘，
再贡献到 C 后不进行逆变换，而是确定了 C 的值后在进行逆变换。

复杂度 $ O(n log^2n) $