概述
首先我们回忆一下多项式卷积：
$$ C_k = \sum_{i + j = k} A_i\times B_j $$
在「算法笔记」快速傅里叶变换 FFT 中我们将多项式 $A(x)$ 和 $B(x)$ 转化为点值表达，然后重新转化为系数表达。
接下来考虑如下卷积形式：
$$ \begin{align*} C_k &= \sum_{i | j = k} A_i\times B_j \\ C_k &= \sum_{i \& j = k} A_i\times B_j \\ C_k &= \sum_{i \oplus j = k} A_i\times B_j \end{align*} $$
其中 $|, \&, \oplus$ 分别表示按位或、按位与、按位异或。
这样就没法使用 $\text{FFT}$ 解决了，我们需要引进新的方法：快速沃尔什变换。
下文会分类介绍这 $3$ 类卷积的解决方法。其中定义部分是一种构造出来的变换方法，证明部分将使用数学归纳法证明一些引理或定理，代码部分为该卷积的实现。
符号表示
首先我们认为下文提及的多项式的长度均为 $2$ 的非负整数次幂。为了方便表述，我们定义如下如下符号及其含义，下文不再赘述。
$$ \begin{array}{} A, B & \text{多项式，其长度为}\ n\text{，次数为}\ n - 1 \\ A_0, A_1 & \text{多项式}\ A\ \text{的前}\ \frac{n}{2}\ \text{位、后}\ \frac{n}{2}\ \text{位} \\ A + B & \text{将多项式}\ A, B\ \text{对应位加（减、乘），} \\ & \text{其系数表达式为}\ (A_0 + B_0, A_1 + B_1, \cdots, A_{n - 1} + B_{n - 1}) \\ A \oplus B & \text{将多项式}\ A, B\ \text{异或（与、或）卷积，} \\ & \text{其系数表达式为}\ (\sum_{i \oplus j = 0} A_i \times B_j, \sum_{i \oplus j = 1} A_i \times B_j, \cdots, \sum_{i \oplus j = n - 1} A_i \times B_j) \\ \text{FWT}(A) & \text{多项式}\ A\ \text{的 FWT 变换} \\ (A, B) & \text{将多项式}\ A, B\ \text{前后拼接起来} \end{array} $$
其中需要尤其注意：这里定义的多项式异或、与、或均为卷积形式！并不是对应系数位运算！
或卷积
定义
$$ \text{FWT}(A) = \begin{cases} (\text{FWT}(A_0), \text{FWT}(A_0 + A_1)) & n > 1 \\ A & n = 1 \end{cases} $$
证明
两个多项式相加后的 $\text{FWT}$ 变换等于分别 $\text{FWT}$ 的和：$\text{FWT}(A + B) = \text{FWT}(A) + \text{FWT}(B)$
当 $n = 1$ 时
$$ \begin{align*} \text{FWT}(A + B) & = A + B \\ & = \text{FWT}(A) + \text{FWT}(B) \end{align*} $$
当 $n > 1$ 时
$$ \begin{align*} \text{FWT}(A + B) & = (\text{FWT}(A_0 + B_0), \text{FWT}(A_0 + A_1 + B_0 + B_1)) \\ & = (\text{FWT}(A_0) + \text{FWT}(B_0), \text{FWT}(A_0) + \text{FWT}(A_1) + \text{FWT}(B_0) + \text{FWT}(B_1)) \\ & = (\text{FWT}(A_0) , \text{FWT}(A_0) + \text{FWT}(A_1)) + (\text{FWT}(B_0), \text{FWT}(B_0) + \text{FWT}(B_1)) \\ & = \text{FWT}(A) + \text{FWT}(B) \end{align*} $$
两个多项式或卷积的 $\text{FWT}$ 变换等于分别 $\text{FWT}$ 的积：$\text{FWT}(A | B) = \text{FWT}(A)\times FWT(B)$
当 $n = 1$ 时
$$ \begin{align*} \text{FWT}(A | B) & = A \times B \\ & = \text{FWT}(A) \times \text{FWT}(B) \end{align*} $$
当 $n > 1$ 时
$$ \begin{align*} \text{FWT}(A | B) & = \text{FWT}((A | B)_0, (A | B)_1) \\ & = \text{FWT}(A_0 | B_0, A_0 | B_1 + A_1 | B_0 + A_1 | B_1) \\ & = (\text{FWT}(A_0 | B_0), \text{FWT}(A_0 | B_0 + A_0 | B_1 + A_1 | B_0 + A_1 | B_1)) \\ & = (\text{FWT}(A_0) \times \text{FWT}(B_0), \\ & \qquad \text{FWT}(A_0) \times \text{FWT}(B_0) + \text{FWT}(A_0) \times \text{FWT}(B_1) + \text{FWT}(A_1) \times \text{FWT}(B_0) + \text{FWT}(A_1) \times \text{FWT}(B_1)) \\ & = (\text{FWT}(A_0) \times \text{FWT}(B_0), (\text{FWT}(A_0) + \text{FWT}(A_1)) \times (\text{FWT}(B_0) + \text{FWT}(B_1))) \\ & = (\text{FWT}(A_0) \times \text{FWT}(B_0), \text{FWT}(A_0 + A_1) \times \text{FWT}(B_0 + B_1)) \\ & = (\text{FWT}(A_0), \text{FWT}(A_0 + A_1)) \times (\text{FWT}(B_0), \text{FWT}(B_0 + B_1)) \\ & = \text{FWT}(A)\times \text{FWT}(B) \end{align*} $$
逆变换
$$ \text{FWT}(A) = (\text{FWT}(A_0), \text{FWT}(A_0) + \text{FWT}(A_1)) \\ \text{IFWT}(A) = (\text{IFWT}(A_0), \text{IFWT}(A_1) - \text{IFWT}(A_0)) $$
代码
void FWTor(std::vector<int> &a, bool rev) {
int n = a.size();
for (int l = 2, m = 1; l <= n; l <<= 1, m <<= 1) {
for (int j = 0; j < n; j += l) for (int i = 0; i < m; i++) {
if (!rev) add(a[i + j + m], a[i + j]);
else sub(a[i + j + m], a[i + j]);
}
}
}与卷积
定义
$$ \text{FWT}(A) = \begin{cases} (\text{FWT}(A_0 + A_1), \text{FWT}(A_1)) & n > 1 \\ A & n = 1 \end{cases} $$
证明
两个多项式相加后的 $\text{FWT}$ 变换等于分别 $\text{FWT}$ 的和：$\text{FWT}(A + B) = \text{FWT}(A) + \text{FWT}(B)$
当 $n = 1$ 时
$$ \begin{align*} \text{FWT}(A + B) & = A + B \\ & = \text{FWT}(A) + \text{FWT}(B) \end{align*} $$
当 $n > 1$ 时
$$ \begin{align*} \text{FWT}(A + B) & = (\text{FWT}(A_0 + A_1 + B_0 + B_1), \text{FWT}(A_1 + B_1)) \\ & = (\text{FWT}(A_0) + \text{FWT}(A_1) + \text{FWT}(B_0) + \text{FWT}(B_1), \text{FWT}(A_1) + \text{FWT}(B_1)) \\ & = (\text{FWT}(A_0) + \text{FWT}(A_1), \text{FWT}(A_1)) + (\text{FWT}(B_0) + \text{FWT}(B_1), \text{FWT}(B_1)) \\ & = \text{FWT}(A) + \text{FWT}(B) \end{align*} $$
两个多项式与卷积的 $\text{FWT}$ 变换等于分别 $\text{FWT}$ 的积：$\text{FWT}(A \& B) = \text{FWT}(A)\times FWT(B)$
当 $n = 1$ 时
$$ \begin{align*} \text{FWT}(A \& B) & = A \times B \\ & = \text{FWT}(A) \times \text{FWT}(B) \end{align*} $$
当 $n > 1$ 时
$$ \begin{align*} \text{FWT}(A \& B) & = \text{FWT}((A \& B)_0, (A \& B)_1) \\ & = \text{FWT}(A_0 \& B_0 + A_1 \& B_0 + A_0 \& B_1, A_1 \& B_1) \\ & = (\text{FWT}(A_0 \& B_0 + A_1 \& B_0 + A_0 \& B_1 + A_1 \& B_1), \text{FWT}(A_1 \& B_1)) \\ & = (\text{FWT}(A_0) \times \text{FWT}(B_0) + \text{FWT}(A_0) \times \text{FWT}(B_1) + \text{FWT}(A_1) \times \text{FWT}(B_0) + \text{FWT}(A_1) \times \text{FWT}(B_1), \\ & \qquad \text{FWT}(A_1) \times \text{FWT}(B_1)) \\ & = ((\text{FWT}(A_0) + \text{FWT}(A_1)) \times (\text{FWT}(B_0) + \text{FWT}(B_1)), \text{FWT}(A_1) \times \text{FWT}(B_1)) \\ & = (\text{FWT}(A_0 + A_1) \times \text{FWT}(B_0 + B_1), \text{FWT}(A_1) \times \text{FWT}(B_1)) \\ & = (\text{FWT}(A_0 + A_1), \text{FWT}(A_1)) \times (\text{FWT}(B_0 + B_1), \text{FWT}(B_1)) \\ & = \text{FWT}(A)\times \text{FWT}(B) \end{align*} $$
逆变换
$$ \text{FWT}(A) = (\text{FWT}(A_0) + \text{FWT}(A_1), \text{FWT}(A_1)) \\ \text{IFWT}(A) = (\text{IFWT}(A_0) - \text{IFWT}(A_1), \text{IFWT}(A_1)) $$
代码
void FWTand(std::vector<int> &a, bool rev) {
int n = a.size();
for (int l = 2, m = 1; l <= n; l <<= 1, m <<= 1) {
for (int j = 0; j < n; j += l) for (int i = 0; i < m; i++) {
if (!rev) add(a[i + j], a[i + j + m]);
else sub(a[i + j], a[i + j + m]);
}
}
}异或卷积
定义
$$ \text{FWT}(A) = \begin{cases} (\text{FWT}(A_0 + A_1), \text{FWT}(A_0 -A_1)) & n > 1 \\ A & n = 1 \end{cases} $$
证明
两个多项式相加后的 $\text{FWT}$ 变换等于分别 $\text{FWT}$ 的和：$\text{FWT}(A + B) = \text{FWT}(A) + \text{FWT}(B)$
当 $n = 1$ 时
$$ \begin{align*} \text{FWT}(A + B) & = A + B \\ & = \text{FWT}(A) + \text{FWT}(B) \end{align*} $$
当 $n > 1$ 时
$$ \begin{align*} \text{FWT}(A + B) & = (\text{FWT}(A_0 + A_1 + B_0 + B_1), \text{FWT}(A_0 - A_1 + B_0 - B_1)) \\ & = (\text{FWT}(A_0) + \text{FWT}(A_1) + \text{FWT}(B_0) + \text{FWT}(B_1), \text{FWT}(A_0) - \text{FWT}(A_1) + \text{FWT}(B_0) - \text{FWT}(B_1)) \\ & = (\text{FWT}(A_0) + \text{FWT}(A_1), \text{FWT}(A_0) - \text{FWT}(A_1)) + (\text{FWT}(B_0) + \text{FWT}(B_1), \text{FWT}(B_0) - \text{FWT}(B_1)) \\ & = \text{FWT}(A) + \text{FWT}(B) \end{align*} $$
两个多项式异或卷积的 $\text{FWT}$ 变换等于分别 $\text{FWT}$ 的积：$\text{FWT}(A \oplus B) = \text{FWT}(A)\times FWT(B)$
当 $n = 1$ 时
$$ \begin{align*} \text{FWT}(A \oplus B) & = A \times B \\ & = \text{FWT}(A) \times \text{FWT}(B) \end{align*} $$
当 $n > 1$ 时
$$ \begin{align*} \text{FWT}(A \oplus B) & = \text{FWT}((A \oplus B)_0, (A \oplus B)_1) \\ & = \text{FWT}(A_0 \oplus B_0 + A_1 \oplus B_1, A_0 \oplus B_1 + A_1 \oplus B_0) \\ & = (\text{FWT}(A_0 \oplus B_0 + A_1 \oplus B_1 + A_0 \oplus B_1 + A_1 \oplus B_0), \text{FWT}(A_0 \oplus B_0 + A_1 \oplus B_1 - A_0 \oplus B_1 - A_1 \oplus B_0)) \\ & = (\text{FWT}(A_0) \times \text{FWT}(B_0) + \text{FWT}(A_1) \times \text{FWT}(B_1) + \text{FWT}(A_0) \times \text{FWT}(B_1) + \text{FWT}(A_1) \times \text{FWT}(B_0), \\ & \qquad \text{FWT}(A_0) \times \text{FWT}(B_0) + \text{FWT}(A_1) \times \text{FWT}(B_1) - \text{FWT}(A_0) \times \text{FWT}(B_1) - \text{FWT}(A_1) \times \text{FWT}(B_0)) \\ & = ((\text{FWT}(A_0) + \text{FWT}(A_1)) \times (\text{FWT}(B_0) + \text{FWT}(B_1)), (\text{FWT}(A_0) - \text{FWT}(A_1)) \times (\text{FWT}(B_0) - \text{FWT}(B_1))) \\ & = (\text{FWT}(A_0 + A_1) \times \text{FWT}(B_0 + B_1), \text{FWT}(A_0 - A_1) \times \text{FWT}(B_0 - B_1)) \\ & = (\text{FWT}(A_0 + A_1), \text{FWT}(A_0 - A_1)) \times (\text{FWT}(B_0 + B_1), \text{FWT}(B_0 - B_1)) \\ & = \text{FWT}(A)\times \text{FWT}(B) \end{align*} $$
逆变换
$$ \text{FWT}(A) = (\text{FWT}(A_0) + \text{FWT}(A_1), \text{FWT}(A_0) - \text{FWT}(A_1)) \\ \text{IFWT}(A) = \left(\frac{\text{IFWT}(A_0) + \text{IFWT}(A_1)}{2}, \frac{\text{IFWT}(A_0) - \text{IFWT}(A_1)}{2}\right) $$
代码
void FWTxor(std::vector<int> &a, bool rev) {
int n = a.size(), inv2 = (P + 1) >> 1;
for (int l = 2, m = 1; l <= n; l <<= 1, m <<= 1) {
for (int j = 0; j < n; j += l) for (int i = 0; i < m; i++) {
int x = a[i + j], y = a[i + j + m];
if (!rev) {
a[i + j] = (x + y) % P;
a[i + j + m] = (x - y + P) % P;
} else {
a[i + j] = 1LL * (x + y) * inv2 % P;
a[i + j + m] = 1LL * (x - y + P) * inv2 % P;
}
}
}
}完整代码
#include <cstdio>
#include <algorithm>
#include <vector>
const int P = 998244353;
void add(int &x, int y) {
(x += y) >= P && (x -= P);
}
void sub(int &x, int y) {
(x -= y) < 0 && (x += P);
}
struct FWT {
int extend(int n) {
int N = 1;
for (; N < n; N <<= 1);
return N;
}
void FWTor(std::vector<int> &a, bool rev) {
int n = a.size();
for (int l = 2, m = 1; l <= n; l <<= 1, m <<= 1) {
for (int j = 0; j < n; j += l) for (int i = 0; i < m; i++) {
if (!rev) add(a[i + j + m], a[i + j]);
else sub(a[i + j + m], a[i + j]);
}
}
}
void FWTand(std::vector<int> &a, bool rev) {
int n = a.size();
for (int l = 2, m = 1; l <= n; l <<= 1, m <<= 1) {
for (int j = 0; j < n; j += l) for (int i = 0; i < m; i++) {
if (!rev) add(a[i + j], a[i + j + m]);
else sub(a[i + j], a[i + j + m]);
}
}
}
void FWTxor(std::vector<int> &a, bool rev) {
int n = a.size(), inv2 = (P + 1) >> 1;
for (int l = 2, m = 1; l <= n; l <<= 1, m <<= 1) {
for (int j = 0; j < n; j += l) for (int i = 0; i < m; i++) {
int x = a[i + j], y = a[i + j + m];
if (!rev) {
a[i + j] = (x + y) % P;
a[i + j + m] = (x - y + P) % P;
} else {
a[i + j] = 1LL * (x + y) * inv2 % P;
a[i + j + m] = 1LL * (x - y + P) * inv2 % P;
}
}
}
}
std::vector<int> Or(std::vector<int> a1, std::vector<int> a2) {
int n = std::max(a1.size(), a2.size()), N = extend(n);
a1.resize(N), FWTor(a1, false);
a2.resize(N), FWTor(a2, false);
std::vector<int> A(N);
for (int i = 0; i < N; i++) A[i] = 1LL * a1[i] * a2[i] % P;
FWTor(A, true);
return A;
}
std::vector<int> And(std::vector<int> a1, std::vector<int> a2) {
int n = std::max(a1.size(), a2.size()), N = extend(n);
a1.resize(N), FWTand(a1, false);
a2.resize(N), FWTand(a2, false);
std::vector<int> A(N);
for (int i = 0; i < N; i++) A[i] = 1LL * a1[i] * a2[i] % P;
FWTand(A, true);
return A;
}
std::vector<int> Xor(std::vector<int> a1, std::vector<int> a2) {
int n = std::max(a1.size(), a2.size()), N = extend(n);
a1.resize(N), FWTxor(a1, false);
a2.resize(N), FWTxor(a2, false);
std::vector<int> A(N);
for (int i = 0; i < N; i++) A[i] = 1LL * a1[i] * a2[i] % P;
FWTxor(A, true);
return A;
}
} fwt;
int main() {
int n;
scanf("%d", &n);
std::vector<int> a1(n), a2(n);
for (int i = 0; i < n; i++) scanf("%d", &a1[i]);
for (int i = 0; i < n; i++) scanf("%d", &a2[i]);
std::vector<int> A;
A = fwt.Or(a1, a2);
for (int i = 0; i < n; i++) {
printf("%d%c", A[i], " \n"[i == n - 1]);
}
A = fwt.And(a1, a2);
for (int i = 0; i < n; i++) {
printf("%d%c", A[i], " \n"[i == n - 1]);
}
A = fwt.Xor(a1, a2);
for (int i = 0; i < n; i++) {
printf("%d%c", A[i], " \n"[i == n - 1]);
}
return 0;
}吐槽
为什么网络上的 $\text{FWT}$ 文章里证明这么简略啊？害得我花了一个上午才证明完，因此本文可能是证明最详细的一篇了吧！
3 条评论
请问如果计算 $\displaystyle c_i = \sum_{j \oplus k = i, j \& k = 0} a_j b_k$ 该如何用FWT呢
直接子集和卷积吧 qaq
蟹蟹~