FWT 学习笔记

· · 算法·理论

前言

怎么都会 FWT。

感觉写的好多，好繁杂，把一个不难的东西讲的很恶心的样子。另外，公式恐惧症患者需要克服一下。

本文在经过修改之后可能还出现了不少疏漏，请审核员或者是广大同学们不吝指出。

定义

FWT 是一种用来求位运算卷积的算法。

先讲一下什么叫做位运算卷积。位运算卷积就是指两个数组 A,B 做以下运算得到 C：

C_i=\sum_{j\oplus k = i}A_j \times B_k

其中 \oplus 是指一种位运算，即 and、or 和 xor 等。

序列 A,B,C 以及在下文提到的 F(A),F(B),F(C),IF(A),IF(B),IF(C) 都默认从 0 开始。但是由于作者的习惯，在代码那一段把它们强制从 1 开始了。

::::info[题外话]{open}

注意到当 \oplus 为 + 运算时式子是这个样子：

C_i=\sum_{j + k = i}A_j \times B_k

这正是我们 FFT/NTT 处理的 + 卷积，俗称多项式乘法。 ::::

方法讲述

FFT/NTT 的处理方式虽然和 FWT 不同，但是其思想和 FWT 是相同的。都是先进行一个正变换，然后逐位相乘，最后经过逆变换得到答案。

那到底怎么变换呢？由于 FWT 所涉及的位运算大多都是 and、or 和 xor 中间的一个，而这三种位运算的处理方式也是不太相同的。我将会分别讲述。

or 卷积

不妨使用 | 来代表 or 运算，因此我们求的是：

C_i=\sum_{j | k = i}A_j \times B_k

正变换 FWT

不难注意到存在一个显然的性质：若 j|i=i,k|i=i，则 (j|k)|i=i。因为前面的条件意味着 j,k 为 i 在二进制上的子集，而 j|k 显然也是 i 的子集。

然后我们的 FWT 是怎么操作的呢？它构造了一个数组：

F(A)_i=\sum_{j|i=i} A_j

就是指每一个位置的子集对应的位置上的数之和。

这样就是 FWT 的正变换，以后都将对于数组 A 做的正变换为 F(A)。

那么，我们要对这个 F(A) 和 F(B) 进行逐位相乘的工作，那么这个 F(A) 和 F(B) 乘起来又哪些很牛的优势呢？请看下文推导：

\begin{aligned} F(A)_i\times F(B)_i &= (\sum_{j|i=i}A_j)(\sum_{k|i=i} B_k)\\ &=\sum_{j|i=i}\sum_{k|i=i} A_j B_k \\ &=\sum_{(j|k)|i=i} A_j B_k \\ &=\sum_{x|i=i} \sum_{j|k=x} A_j B_k \\ &=\sum_{x|i=i} C_x \\ &=F(C)_i \end{aligned}

前两个等号都是基本操作，第三个等号运用了之前的结论，第四个等号是基本操作，第五个等号运用了 C 的定义，第六个等号运用了 F(C) 的定义。

那么根据这个式子你发现什么了？没错，直接把 F(A) 和 F(B) 大力乘起来就是 F(C)！我们在之后做逆变换就可以了！

但是我们还有一个问题，就是如何快速求出 F(A)。显然有 O(3^{\log_2{n}}) 的暴力做法（一共有 \log_2{n} 位，而暴力计算相当于子集枚举）。但我们并不满足。

回忆 FFT/NTT 处理卷积问题的过程，不难想到 FFT/NTT 是先将 n 变成一个 2 的整数次幂，然后使用分治（至少基础的形态是这样）处理。而 FWT 正是效仿了这一点。

对于一个长度为 2^a 的数组，我们可以将前 2^{a-1} 个数字组成的数组定义为 A_0，其余部分定义为 A_1。

考虑这样定义有什么用处。A_0 中的位置由于在二进制中的第 a 位为 0，所以其子集还是在 A_0 中。而 A_1 就不一样了，A_1 中的位置在二进制中的第 a 位为 1，所以其子集不仅可以在自己里面，还可以在 A_0 里面。

结合分治思想，我们可以列出以下式子：

简单的复杂度分析可以发现这样的复杂度是 O(n \log n) 的。这就是分治的妙处，起到了一个后面从前面借力的作用，从而删去了很多重复计算。

逆变换 IFWT

不要忘记先逐位相乘。

设对 A 进行逆变换的结果为 IF(A)。那么 A=IF(F(A))。思考，怎么进行一个 IFWT 的过程？

给出做法，只有一句话：把正变换的符号换一下就行了，其余都和正变换一模一样。

可能有人会不太懂，描述成式子就是，原来的 F(A)=\text{merge}(F(A_0),F(A_1)+F(A_0)) 现在变成了 F(A)=\text{merge}(F(A_0),F(A_1)-F(A_0))。

感性理解就像是正变换是前缀和，逆变换是差分。证明看文献，不想写了/tuu。

and 卷积

不妨使用 & 来代表 and 运算，因此我们求的是：

C_i=\sum_{j \& k = i}A_j \times B_k

正变换 FWT

注意到 and 和 or 似乎在很多方面上都相反。所以我们考虑把子集和反过来，也就是超集和，得出 F(A) 的构造方式：

F(A)_i=\sum_{j|i=j} A_j

而根据 or 卷积的经验，我们需要对 F(A) 和 F(B) 进行逐位相乘的工作。那么究竟能不能直接逐位相乘呢？我们仍然需要一些推导。

注意到显然当 j|i=j,k|i=k 时，有 (j\&k)|i=(j\&k)。

\begin{aligned} F(A)_i\times F(B)_i &= (\sum_{j|i=j}A_j)(\sum_{k|i=k} B_k)\\ &=\sum_{j|i=j}\sum_{k|i=k} A_j B_k \\ &=\sum_{(j\&k)|i=(j\&k)} A_j B_k \\ &=\sum_{x|i=x} \sum_{j\&k=x} A_j B_k \\ &=\sum_{x|i=x} C_x \\ &=F(C)_i \end{aligned}

因此我们仍然可以直接在正变换后直接逐位相乘。现在的问题还是如何快速求出 F(A)。

仍然使用分治做法。先把 n 变成一个 2 的正整数次幂。然后对于一个长度为 2^a 的数组，我们把前 2^{a-1} 个数字组成的数组定义为 A_0，其余部分定义为 A_1。

分治的方法也就是平凡的了。

逆变换 IFWT

和 or 卷积差不多，依旧把正变换的符号换一下，然后再做一遍正变换就行了。

感性上的理解仍然是正变换是前缀和，逆变换是差分。

xor 卷积

下文使用 \oplus 来表示 xor。

C_i=\sum_{j \oplus k = i}A_j \times B_k

正变换 FWT

这时候就比较困难了。xor 和 and 或 or 的联系都不大。

仿照 and 和 or 的做法，考虑仍然构造一个 F(A)，然后依据 F(A) 进行 FWT 正变换，则 F(A) 应该是这个样子：

F(A)_i=\sum_{j=0}^n f(i,j) A_j

我们的目标就是，构造 F(A)_i（相当于构造 f(i,j)），使得我们可以直接让 F(A) 和 F(B) 逐位相乘得到 F(C)。

直接构造很困难。回想，我们是怎么证明 F(A) 直接和 F(B) 逐位相乘就可以得到 F(C) 的？

我们第一步就是先直接展开。所以不难得出，我们的 f(i,j) 需要做到：

\sum_{j=0}^n f(i,j) C_j = (\sum_{j=0}^n f(i,j) A_j)(\sum_{k=0}^n f(i,k) B_k)

因为有这个 C_j 在，我们很不舒服。所以我们把 C_j 按照其定义代换：

\sum_{j=0}^n f(i,j) (\sum_{a \oplus b = j}A_a B_b) = (\sum_{j=0}^n f(i,j) A_j)(\sum_{k=0}^n f(i,k) B_k)

代数变换得到以下式子：

\sum_{j=0}^n \sum_{k=0}^n f(i,j\oplus k) A_j B_k = \sum_{j=0}^n\sum_{k=0}^n f(i,j)f(i,k) A_j B_k

然后我们注意到，欸这个 A_j B_k 是不是不太需要啊？我们只要让对于每一个 0 \le i,j,k \le n，f(i,j\oplus k)=f(i,j) f(i,k) 这个条件成立，那么上面这个式子就一定成立了！

那么我们该怎么构造呢？（下面要有些注意力了说白了就是笔者不知道是怎么想到的）

首先有一个结论：\text{popcount}(a)+\text{popcount}(b)\equiv \text{popcount}(a \oplus b) (\bmod \ 2)。这是好证的。那么该如何利用这个结论构造？

注意到，(-1)^x 的值也和 x 的奇偶性有关。而根据上面的结论，我们不难想到构造 f(i,j) 等于 (-1)^x，其中 x 应该是一个和 i,j 都有关的东西。

而注意到 x=|i \cap j| 是 f(i,j\oplus k)=f(i,j)f(i,k) 一定成立。所以就构造出来了：

f(i,j)=(-1)^{|i \cap j|}

那么也就一定有 F(A)_i F(B)_i=F(C)_i 了。现在需要考虑如何快速计算 F(A)。

那么依旧考虑分治。把 n 变成 2 的正整数次幂之后，设当前要计算的 F(A) 的规模是 2^a（注意是当前需要计算的，也就是说，A 的长度未必等于 n），进行分治：

这样就可以在 O(n \log n) 的时间内完成 FWT 正变换。

逆变换 IFWT

就是把 F(A_0)+F(A_1),F(A_0)-F(A_1) 都除以 2 就可以了。

感性一点理解的话，就是直接移项然后和差状物。

代码实现

虽然我前面给出的做法可以直接递归模拟，但是递归的常数比较大。所以为了避免被卡常，所以要使用循环。

给出循环的代码，可以自己理解一下代码的含义是什么。另外，建议打这些什么什么变换的都使用函数封装。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1000010, mod = 998244353;
int a[N], b[N];
int x[N], y[N];
int n;

void mul() {
    for (int i = 1; i <= n; i++)
        x[i] = x[i] * y[i] % mod;
}

void mem() {
    for (int i = 1; i <= n; i++)
        x[i] = a[i], y[i] = b[i];
}

void outp() {
    for (int i = 1; i <= n; i++)
        cout << x[i] << " ";
    cout << endl;
}

void OR(int *a, int op) {
    for (int i = 1; i < n; i *= 2) {
        int siz = i * 2;
        for (int j = 1; j <= n; j += siz)
            for (int k = 0; k < i; k++)
                a[i + j + k] = (a[i + j + k] + a[j + k] * op % mod + mod) % mod;
    }
}

void AND(int *a, int op) {
    for (int i = 1; i < n; i *= 2) {
        int siz = i * 2;
        for (int j = 1; j <= n; j += siz)
            for (int k = 0; k < i; k++)
                a[j + k] = (a[j + k] + a[i + j + k] * op % mod + mod) % mod;
    }
}

void XOR(int *a, int op) {
    for (int i = 1; i < n; i *= 2) {
        int siz = i * 2;
        for (int j = 1; j <= n; j += siz)
            for (int k = 0; k < i; k++) {
                int xx = a[j + k], yy = a[i + j + k];
                a[j + k] = (xx + yy) % mod * op % mod, a[i + j + k] = (xx - yy + mod) % mod * op % mod;
            }
    }
}

signed main() {
    cin >> n;
    n = (1 << n);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    mem(), OR(x, 1), OR(y, 1), mul(), OR(x, -1), outp();
    mem(), AND(x, 1), AND(y, 1), mul(), AND(x, -1), outp();
    mem(), XOR(x, 1), XOR(y, 1), mul(), XOR(x, (mod + 1) / 2), outp();
    return 0;
}

参考文献