快速沃尔什变换（FWT）学习小结

Imagine · 2018-06-04 16:12:03 · 个人记录

注：关于部分内容的证明，由于网上的博客或一些论文对其已有详细的介绍，故这里不再赘述。

概念

通俗地讲，有时我们希望能够快速地解决一类集合卷积问题。其形式如下：

对于一个拥有 n个元素的有限集，已知关于全集的函数 f, g，求函数 h。对于一个集合 S，h_S的运算如下（以下统一用 2^n表示全集）：

其中，\bigoplus是一类集合运算。这里，我们首先以逻辑异或运算 (\rm xor)为例来说明。

在异或意义下，上面的式子又叫做集合对称差卷积。单从上面的式子看不出什么。这里，首先注意到，对于一个集合 S，满足下式：

即当 S为空集时，\frac{1}{2^n}\sum_{T \subseteq 2^n}(-1)^{|S \bigcap T|}为 1，否则为 0。

简单证明如下：

有了这个式子，我们就可以化简上面给出的集合对称差卷积式子：

上面的式子启发了我们定义沃尔什变换：

对于一个集合幂级数 f，我们定义 f的沃尔什变换为集合幂级数 \hat{f}，其中：

\hat{f_S} = \sum_{T \subseteq 2^n}f_T(-1)^{|S \bigcap T|}

反过来，我们定义 \hat{f}的沃尔什逆变换为 f，有 f_S = \frac{1}{2^n}\sum_{T \subseteq 2^n}\hat{f_T}(-1)^{|S \bigcap T|}

此时，我们再来看集合对称差卷积，就得到了：

因此，我们若想求 h = f * g，先对 f, g做沃尔什变换，将对应的系数乘起来得到 \hat{h}，再做沃尔什逆变换即可。

具体的过程如下：

我们可以使用递推，设 \hat{f} _ S ^ {(i)}为只考虑那些与 S的对称差是 \{1, ..., i\}的子集的集合时的沃尔什变换的第 S项，即那些 S \bigoplus T \subseteq \{1, ..., i\}的集合 T的 f_T(-1)^{|S \bigcap T|}之和。令 \hat{f} _ S ^ {(0)} = f_S，容易得到对于每个不包含 i的 S有 \hat{f} _ S ^ {(i)} = \hat{f} _ S ^ {(i - 1)} +\hat{f} _ {S \bigcup \{i\}} ^ {(i - 1)}且 \hat{f} _ {S \bigcup \{i\}} ^ {(i)} = \hat{f} _ S ^ {(i - 1)} -\hat{f} _ {S \bigcup \{i\}} ^ {(i - 1)}。

我们可以做沃尔什变换后乘以 \frac{1}{2^n}得到沃尔什逆变换，于是做沃尔什变换和沃尔什逆变换的时间复杂度都是 {\rm O}(n2^n)。

通俗地说，就是考虑最高位为 0和 1的两种情况，然后将两部分运算的结果拼起来。

以上部分是对 \bigoplus为逻辑异或运算 (\rm xor)时的分析。除此之外，还有和运算 (\rm and)与或运算 (\rm or)。下面一并给出对应集合幂级数运算的代码（具体实现已写在注释，替换函数中的省略号即可。由于实际意义类似，为了方便，在下面的内容中，我们将三种运算对应的变换均称为快速沃尔什变换。函数中，n为全集，当 t = 1时为沃尔什变换， t = -1时为沃尔什逆变换）：

/*
 *    FWT                                       UFWT
 * &: a[j + k] = p + q                          a[j + k] = p - q
 * |: a[i + j + k] = p + q                      a[i + j + k] = q - p
 * ^: a[j + k] = p + q, a[i + j + k] = p - q    a[j + k] = (p + q) / 2, a[i + j + k] = (p - q) / 2
 */

void FWT(int* a, int t) {
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j += (i << 1)) {
            for (int k = 0; k < i; k++) {
                int p = a[j + k], q = a[i + j + k];
                if (t == 1) ...
                else ...
            }
        }
    }
}

关于FWT的一些性质与具体使用将在下面的例题当中提到。

例题

（直观起见，在下面的例题中我们统一将构造的生成函数简称为函数）

1. [CSU1911] \rm Card\ Game

题意：给定两个由 n个数组成的数组 a, b，求从 a, b中分别选出一个数，或运算结果为 x的方案数。多组询问，n \leq 10^5, a_i, b_i \leq 2^{18}。

分析：FWT模板题目。以数值为下标，将两个数组直接做或卷积即可。注意输入的数为二进制形式。

代码

2. [CF662C] \rm Binary\ Table

题意：给定一个01矩阵，每次可以选择一行或一列，将其中所有的数字翻转(0 → 1, 1 → 0)，求矩阵中的1最少会有多少个。n \leq 20, m \leq 10^5。

分析：一个显然的暴力是 2^n枚举选择哪些行翻转，那么对于每一列，这一列的贡献为该列中0的数量和1的数量中的较小值。但由于 m很大，因此这样做时间无法承受。

注意到 n \leq 20，因此每一列我们可以看成一个有 n位的二进制数。对于 [0, 2^n - 1]里的每一个数，我们都可以先预处理一个数组 b_S，表示二进制数 S中0,1数量的较小值。注意到如果某一列的状态为 S_1，要操作的行（我们也把它看成二进制数）为 S_2，那么该列最后实际上的状态为 S_1\ {\rm xor}\ S_2。我们记录数组 a， a_S表示最开始有多少列的状态为 S，那么对于一个操作行状态 k，最终的答案 f_k有： \begin{aligned}f_k &= \sum_{S_1}\sum_{S_2}[S_1\ {\rm xor}\ k = S_2]a_{S_1}b_{S_2}\\ &= \sum_{S_1}\sum_{S_2}[S_1\ {\rm xor}\ S_2 = k]a_{S_1}b_{S_2}\end{aligned}

因此我们直接将 a, b做异或卷积即可。

代码

3. [HDU5823] \rm Color\ II

题意：定义一张无向图的价值为：给每个结点染色，使得不存在两个有边直接连接的结点颜色相同的最少颜色数。给定一张 n个点的无向图，求该图的 2^n - 1张非空子图的价值。n \leq 18。

分析：设 f_{i, S}表示用 i种颜色给 S集合染色的合法方案数。那么有如下转移：

我们可以预处理出 f_1的情况，即能够染成同一颜色的 S集合为哪些，只需要 2^n枚举集合然后判断是否有连边。通过上面的式子可以看出，我们直接对 f数组做或卷积即可。最后，对于子图 S，满足 f_{p, S} \neq 0的最小的 p即为给子图 S染色所需的最小颜色数。

代码

4. [HDU5909] \rm Tree\ Cutting

题意：给定一棵 n个结点的树，每个点有一个小于 m的权值 v_i，定义一个连通块的权值为连通块内所有点的权值的异或和。求权值为 0, 1, 2, ..., m - 1的连通块的个数。n \leq 1000, m = 2^k, k \leq 10。

分析：先将树转化为有根树，设 f_{i, j}表示以 i为根且权值为 j的连通块个数。那么有如下转移：

其中， k是 i的一个儿子。上面的转移是一个异或卷积的形式，因此我们在对树进行 \rm dfs的时候直接FWT即可。需要注意的是，k 可以为空，即可以选择以 i为根的整颗子树，故计算完 f_i后应让 f_{i, 0}增加 1，以便后面的转移，记得最后将其减去。

代码

5. [BZOJ4589] \rm Hard\ Nim

题意：有 n堆石子，每堆石子的数量都是不超过 m的质数，求有多少种使得先手必败的局面。n \leq 10^9, m \leq 5×10^4。

分析：先手必败的充要条件为所有石子数量的异或和为 0。设 f_{i, j}表示前 i堆石子的异或和为 j的方案数，那么有如下转移：

我们可以将 [v\ \rm is\ prime]看做一个函数 b，当且仅当 i为小于 m的质数时 b_i为 1，那么令函数 a有 a_0 = 1，求 a与 b^n的异或卷积即可。答案为卷积函数的 f_0。

代码

6. [51Nod1773] \rm A国的贸易

题意：给出一个长为 2^n的序列，下标编号为 0至 2^n - 1，每一次操作，下标为 i的序列值会加上所有操作前的下标编号与 i仅相差一个二进制位的序列值。求 k次操作后的序列。n \leq 20, k \leq 10^9。

分析：对于一个编号 x，很明显，所有与它相差一个二进制位的编号一定可以写成 x\ {\rm xor}\ 2^l(l \in [0, n - 1])的形式，因此，对于每一次操作，序列值 a_i有：

我们可以构造一个函数 b，使得满足 x = 2^l(l \in [0, n - 1])的 b_x = 1。要注意，由于 a_i自身的值也会被累加，因此 b_0也要为 1。求原序列 a与 b^k的异或卷积即可。

代码

7. [UOJ310] 黎明前的巧克力

题意：给出 n个数 a_i，求从中选出两个互不相交的集合，满足两个集合的异或和相等的方案数。不允许均为空集。n \leq 10^6, a_i \leq 10^6。

分析：设 f_{i, j}表示前 i个数中选出异或和为 j的方案数。那么转移如下：

即：若不选择 a_i，那么从 f_{i, j}转移过来，若选择 a_i，那么从 f_{i - 1, j\ {\rm xor}\ a_i}转移过来，由于 a_i可以属于 A集合也可以属于 B集合，因此要乘以 2。

根据这个形式，我们可以对于每一个 i，构造一个 b函数，使得 b_0 = 1, b_{a_i} = 2，那么进行 n次FWT，求其乘积，似乎这个问题就解决了。只可惜，这样会超时，很明显无法接受 n次FWT的时间复杂度。

这就需要我们深入发掘FWT的性质。首先，对于每一个 i，令我们构造的 b函数为 b^{(i)}，我们的目的是希望能够得到所有 \hat{b}^{(i)}相乘的结果。那么，这些 \hat{b}^{(i)}究竟由什么组成呢？

观察关于集合幂级数 f的沃尔什变换的式子：

由于对于每一个 i，仅有 b^{(i)}_0 = 1, b^{(i)}_{a_i} = 2，其余的 b^{(i)}均为 0，那么我们代入上面的式子，会发现 \hat{b}^{(i)}的取值仅仅只有两种。由于 b^{(i)}_{0}对\hat{b}^{(i)}的贡献恒为 1（|S \bigcap \emptyset| = 0，因此T = 0时，f_T(-1)^{|S \bigcap T|} = 1×1^0 = 1），而 b^{(i)}_{a_i}会根据交集大小的奇偶造成可正可负的贡献，因此 \hat{b}^{(i)}要么为 1 + 2 = 3，要么为 1 + (-2) = -1。

现在，我们已经清楚了所有的 \hat{b}^{(i)}要么为 3要么为 -1，但我们希望求得他们的乘积，还需要清楚他们的数量。由于FWT的和等于和的FWT，故我们可以先求出所有 b^{(i)}的和，再求其FWT，我们令其为 \hat{f}。

对于 \hat{f}的每一项 \hat{f_S}，由于和仅由若干个 3和 -1加得，我们现在也已经求得了其和值，令其中有 x个 3，那么就有 n - x个 -1，于是我们有 3x - (n - x) = \hat{f_S}

解这个方程，我们终于求得了构成 \hat{f_S}的 3的数量为 \frac{\hat{f_S} + n}{4}，对应地， -1的数量为 n - \frac{\hat{f_S} + n}{4}，那么我们也就得到了所有 \hat{b}^{(i)}相乘的结果，令其为 \hat{g}，那么就有 \hat{g} _ S = 3^{\frac{\hat{f_S} + n}{4}}×(-1)^{n - \frac{\hat{f_S} + n}{4}}

再对 \hat{g}做逆FWT即为最终的答案。

代码

8. \rm[WC2018]州区划分

题意：给定 n个点，每个点有点权 w_i，点与点之间有无向边连接。将其划分为若干个非空不相交集合 V_1, V_2, ...,V_k，且每个集合不能存在欧拉回路。给定 p，定义一次划分的满意度为：

求所有划分方案的满意度之和。n \leq 21,0\leq p \leq 2。

分析：首先我们可以预处理出所有集合是否合法，即是否存在欧拉回路。定义 f_S表示对于集合 S，所有划分方案的满意度之和，g_S表示集合 S的点权和的 p次方（前提是该集合合法）。令 f_0 = 1，那么有如下转移：

化简至此，最右侧的\sum_{S' \in S}f_{S - S'}g_{S'}已经很明显是一个或卷积的形式。但是注意到上面的式子中，求 f时会用到 f，因此我们不能直接上FWT。考虑到转移时，对于当前的 f_S，会用到的 f_{S'}严格满足 |S'|<|S|，因此，我们可以增加一维状态，令 f_{i, S}表示对于集合 S，所有划分方案的满意度之和，集合 S的大小为 i。g同理。这样，我们只需要按 i的顺序，做 n次FWT，问题便得以解决。

代码

9. [HDU6057] \rm Kanade's\ convolution

题意：给定数组 A[0...2^n - 1], B[0...2^n - 1]，求数组 C[0...2^n - 1]，满足 C[k] = \sum_{i\ {\rm and}\ j = k}A[i{\ \rm xor\ }j]B[i{\ \rm or\ }j]