浅谈FWT

§ 1 前言

对于离散卷积式

$$\begin{align} c_n=\sum\limits_{i+j=n}a_ib_j \end{align}$$

我们可以直接使用 $\rm FFT$ 求解。

考虑该问题的扩展，如何求解将 $i+j=n$ 限制中的 $+$ 换成其他运算符的卷积式。

对于 $c_n=\sum\limits_{i-j=n}a_ib_j$，可以将多项式 $B$ 系数反转后进行 $\rm FFT$。

对于 $c_n=\sum\limits_{i\times j=n} a_ib_j$，在模 $p$ 意义下，且 $p$ 有原根 $G$ 时可以将 $i$ 位置的值放到 $\log_G i\pmod{p}$ 位置进行 $\rm NTT$，然后再放回来。

而对于位运算卷积，即

$$\left\lbrace \begin{aligned} c_n=\sum\limits_{i\&j=n}a_ib_j \\ c_n=\sum\limits_{i\,|\,j=n}a_ib_j \\ c_n=\sum\limits_{i\oplus j=n}a_ib_j \end{aligned} \right.$$

可以使用快速沃尔什变换 $(\rm Fast\ Walsh\ Transform,\ FWT)$ 求解。

---

§ 2 快速沃尔什变换

首先声明下文中用到的表示法。

对于一个 $n-1$ 次多项式

$$\begin{align} f(x)=a_0x^0+a_1x^1+a_2x^2+\cdots+a_{n-1}x^{n-1} \end{align}$$

将其表示为

$$\begin{align} (a_0,a_1,a_2,\cdots,a_{n-1}) \end{align}$$

定义多项式加法 $(\rm operator\ +)$ 为

$$\begin{align} C(x)&=A(x)+B(x) \\ &=(a_0,\ a_1,\ a_2,\cdots,\ a_{n-1})+(b_0,\ b_1,\ b_2,\cdots,\ b_{n-1}) \\ &=(a_0+b_0,\ a_1+b_1,\ a_2+b_2,\cdots,\ a_{n-1}+b_{n-1}) \end{align}$$

定义多项式减法 $(\rm operator\ -)$ 为

$$\begin{align} C(x)&=A(x)-B(x) \\ &=(a_0,\ a_1,\ a_2,\cdots,\ a_{n-1})-(b_0,\ b_1,\ b_2,\cdots,\ b_{n-1}) \\ &=(a_0-b_0,\ a_1-b_1,\ a_2-b_2,\cdots,\ a_{n-1}-b_{n-1}) \end{align}$$

定义多项式对应系数乘法 $(\rm operator\ \times)$ 为

$$\begin{align} C(x)&=A(x)\times B(x) \\ &=(a_0,\ a_1,\ a_2,\cdots,\ a_{n-1})\times(b_0,\ b_1,\ b_2,\cdots,\ b_{n-1}) \\ &=(a_0b_0,\ a_1b_1,\ a_2b_2,\cdots,\ a_{n-1}b_{n-1}) \end{align}$$

对于一个位运算符 $\boxtimes\in\lbrace\ |,\ \&,\oplus\rbrace$，定义位运算卷积

$$\begin{align} C(x)&=A(x)\boxtimes B(x) \\ &=(a_0,\ a_1,\ a_2,\cdots,\ a_{n-1})\boxtimes(b_0,\ b_1,\ b_2,\cdots,\ b_{n-1}) \\ &=(\sum\limits_{i\boxtimes j=0}a_ib_j,\sum\limits_{i\boxtimes j=1}a_ib_j,\sum\limits_{i\boxtimes j=2}a_ib_j,\cdots,\sum\limits_{i\boxtimes j=n-1}a_ib_j) \end{align}$$

易证得，$\boxtimes$ 运算具有分配律。

定义多项式拼接运算 $(A,B)$ 为

$$\begin{align} (A,B)&=((a_0,\ a_1,\ a_2,\cdots,\ a_{n-1}),(b_0,\ b_1,\ b_2,\cdots,\ b_{n-1})) \\ &=(a_0,\ a_1,\ a_2,\cdots,\ a_{n-1},b_0,\ b_1,\ b_2,\cdots,\ b_{n-1}) \end{align}$$

对于一个 $2^k-1$ 次的多项式 $A$，令 $A_0$ 为其前 $2^{k-1}$ 项，$A_1$ 为其后 $2^{k-1}$ 项。

代码中出现的常量、变量及函数定义如下：

typedef long long ll;
const int inv2 = 499122177, MOD = 998244353;

inline int add(const int &x, const int &y) {return x + y >= MOD ? x + y - MOD : x + y;}
inline int mul(const int &x, const int &y) {return x * (ll)y % MOD;}

---

§ 2.1 按位或卷积

§ 2.1.1 构造

按位或卷积形式如下

$$\begin{align} C&=A\ |\ B \\ \Longleftrightarrow c_n&=\sum\limits_{i\,|\,j=n}a_ib_j \end{align}$$

定义 ${\rm FWT}(A)$ 为

$$\begin{align} {\rm FWT}(A)=(\sum\limits_{i\,|\,0=0}a_i,\sum\limits_{i\,|\,1=1}a_i,\sum\limits_{i\,|\,2=2}a_i,\cdots,\sum\limits_{i\,|\,(n-1)=(n-1)}a_i) \end{align}$$

容易发现 ${\rm FWT}(A\ |\ B)={\rm FWT}(A)\times{\rm FWT}(B)$，证明如下

$$\begin{align} {\rm FWT}(A)\times{\rm FWT}(B)&=(\sum\limits_{i\,|\,0=0}a_i,\sum\limits_{i\,|\,1=1}a_i,\cdots,\sum\limits_{i\,|\,(n-1)=(n-1)}a_i)\times(\sum\limits_{i\,|\,0=0}b_i,\sum\limits_{i\,|\,1=1}b_i,\cdots,\sum\limits_{i\,|\,(n-1)=(n-1)}b_i) \\ &=(\sum\limits_{i\,|\,0=0}a_i\sum\limits_{j\,|\,0=0}b_j,\sum\limits_{i\,|\,1=1}a_i\sum\limits_{j\,|\,1=1}b_j,\cdots,\sum\limits_{i\,|\,(n-1)=(n-1)}a_i\sum\limits_{j\,|\,(n-1)=(n-1)}b_j) \\ &=(\sum\limits_{i\,|\,j\,|\,0=0}a_ib_j,\sum\limits_{i\,|\,j\,|\,1=1}a_ib_j,\cdots,\sum\limits_{i\,|\,j\,|\,(n-1)=(n-1)}a_ib_j \\ &=(\sum\limits_{k\,|\,0=0}\sum\limits_{i\,|\,j=k}a_ib_j,\sum\limits_{k\,|\,1=1}\sum\limits_{i\,|\,j=k}a_ib_j,\cdots,\sum\limits_{k\,|\,(n-1)=(n-1)}\sum\limits_{i\,|\,j=k}a_ib_j \\ &={\rm FWT}(A\ |\ B) \end{align}$$

所以我们只需寻找 $A\Leftrightarrow{\rm FWT}(A)$ 之间快速变换的方法即可计算出卷积。

§ 2.1.2 快速变换

容易发现，对于一个 $2^n-1$ 次多项式 $A$，有如下结论

• 对于 ${\rm FWT}(A)_0$，只有 ${\rm FWT}(A_0)$ 的对应项有贡献。
• 对于 ${\rm FWT}(A)_1$，${\rm FWT}(A_0)$ 及 ${\rm FWT}(A_1)$ 的对应项均有贡献。

所以有

$${\rm FWT}(A)=\left\lbrace\begin{aligned} &A\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad ,n=1 \\ &({\rm FWT}(A_0),\ {\rm FWT}(A_1)+{\rm FWT}(A_0))\quad,n\neq 1 \end{aligned}\right.$$ $${\rm IFWT}(A)=\left\lbrace\begin{aligned} &A\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad,n=1 \\ &({\rm IFWT}(A_0),\ {\rm IFWT}(A_1)-{\rm IFWT}(A_0))\quad,n\neq 1 \end{aligned}\right.$$

inline void FWT_or(int *A){
	for(register int i = 1; i < lim; i <<= 1)
		for(register int j = 0; j < lim; j += i << 1)
			for(register int k = 0; k < i; k++)
				A[j + k + i] = add(A[j + k + i] , A[j + k]);
}

inline void IFWT_or(int *A){
	for(register int i = 1; i < lim; i <<= 1)
		for(register int j = 0; j < lim; j += i << 1)
			for(register int k = 0; k < i; k++)
				A[j + k + i] = add(A[j + k + i] , MOD - A[j + k]);
}

---

§ 2.2 按位与卷积

按位与卷积形式如下

$$\begin{align} C&=A\ \&\ B \\ \Longleftrightarrow c_n&=\sum\limits_{i\&j=n}a_ib_j \end{align}$$ $$\begin{align} {\rm FWT}(A)=(\sum\limits_{i\&0=0}a_i,\sum\limits_{i\&1=1}a_i,\sum\limits_{i\&2=2}a_i,\cdots,\sum\limits_{i\&(n-1)=(n-1)}a_i) \end{align}$$

处理方式和按位或卷积基本相同，下面直接给出结论

$${\rm FWT}(A)=\left\lbrace\begin{aligned} &A\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad ,n=1 \\ &({\rm FWT}(A_0)+{\rm FWT}(A_1),\ {\rm FWT}(A_1))\quad,n\neq 1 \end{aligned}\right.$$ $${\rm IFWT}(A)=\left\lbrace\begin{aligned} &A\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad,n=1 \\ &({\rm IFWT}(A_0)-{\rm IFWT}(A_1),\ {\rm IFWT}(A_1))\quad,n\neq 1 \end{aligned}\right.$$

inline void FWT_and(int *A){
	for(register int i = 1; i < lim; i <<= 1)
		for(register int j = 0; j < lim; j += i << 1)
			for(register int k = 0; k < i; k++)
				A[j + k] = add(A[j + k] , A[j + k + i]);
}

inline void IFWT_and(int *A){
	for(register int i = 1; i < lim; i <<= 1)
		for(register int j = 0; j < lim; j += i << 1)
			for(register int k = 0; k < i; k++)
				A[j + k] = add(A[j + k] , MOD - A[j + k + i]);
}

---

§ 2.3 按位异或卷积

按位异或卷积形式如下

$$\begin{align} C&=A\oplus B \\ \Longleftrightarrow c_n&=\sum\limits_{i\oplus j=n}a_ib_j \end{align}$$ $$\begin{align} {\rm FWT}(A)=(\sum\limits_{i\oplus 0=0}a_i,\sum\limits_{i\oplus 1=1}a_i,\sum\limits_{i\oplus 2=2}a_i,\cdots,\sum\limits_{i\oplus (n-1)=(n-1)}a_i) \end{align}$$

处理方式和前两个位运算卷积基本相同，证明见 zyh 巨爷的博文，下面直接给出结论

$${\rm FWT}(A)=\left\lbrace\begin{aligned} &A\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad\ \ ,n=1 \\ &({\rm FWT}(A_0)+{\rm FWT}(A_1),\ {\rm FWT}(A_0)-{\rm FWT}(A_1))\quad,n\neq 1 \end{aligned}\right.$$ $${\rm IFWT}(A)=\left\lbrace\begin{aligned} &A\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\ \ ,n=1 \\ &\left(\frac{ {\rm IFWT}(A_0)+{\rm IFWT}(A_1)}{2},\ \frac{ {\rm IFWT}(A_0)-{\rm IFWT}(A_1)}{2}\right)\quad,n\neq 1 \end{aligned}\right.$$

inline void FWT_xor(int *A){
	for(register int i = 1; i < lim; i <<= 1)
		for(register int j = 0; j < lim; j += i << 1)
			for(register int k = 0; k < i; k++){
				const int L = A[j + k], R = A[j + k + i];
				A[j + k] = add(L, R), A[j + k + i] = add(L, MOD - R);
			}
}

inline void IFWT_xor(int *A){
	for(register int i = 1; i < lim; i <<= 1)
		for(register int j = 0; j < lim; j += i << 1)
			for(register int k = 0; k < i; k++){
				const int L = A[j + k], R = A[j + k + i];
				A[j + k] = add(L, R), A[j + k + i] = add(L, MOD - R);
				A[j + k] = mul(A[j + k], inv2), A[j + k + i] = mul(A[j + k + i], inv2);
			}
}

---

§ 3 模板题

=> luogu 4717 【模板】快速沃尔什变换

§ 3.1 题意

给定长度为 $2^n$ 的两个多项式 $A,\ B$，设 $C_i=\sum\limits_{j\boxtimes k=i}A_jB_k$。

求出当 $\boxtimes$ 分别为 ${\rm or},\ {\rm and},\ {\rm xor}$ 时的 $C$。

$0\leq n\leq 17$。

§ 3.2 代码

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int inv2 = 499122177, MOD = 998244353;

inline void getint(int &num){
	register int ch, neg = 0;
	while(!isdigit(ch = getchar())) if(ch == '-') neg = 1;
	num = ch & 15;
	while(isdigit(ch = getchar())) num = num * 10 + (ch & 15);
	if(neg) num = -num;
}

inline int add(const int &x, const int &y) {return x + y >= MOD ? x + y - MOD : x + y;}
inline int mul(const int &x, const int &y) {return x * (ll)y % MOD;}

int n, lim, A[131080], B[131080], C[131080];

inline void FWT_or(int *A){
	for(register int i = 1; i < lim; i <<= 1)
		for(register int j = 0; j < lim; j += i << 1)
			for(register int k = 0; k < i; k++)
				A[j + k + i] = add(A[j + k + i] , A[j + k]);
}

inline void IFWT_or(int *A){
	for(register int i = 1; i < lim; i <<= 1)
		for(register int j = 0; j < lim; j += i << 1)
			for(register int k = 0; k < i; k++)
				A[j + k + i] = add(A[j + k + i] , MOD - A[j + k]);
}

inline void FWT_and(int *A){
	for(register int i = 1; i < lim; i <<= 1)
		for(register int j = 0; j < lim; j += i << 1)
			for(register int k = 0; k < i; k++)
				A[j + k] = add(A[j + k] , A[j + k + i]);
}

inline void IFWT_and(int *A){
	for(register int i = 1; i < lim; i <<= 1)
		for(register int j = 0; j < lim; j += i << 1)
			for(register int k = 0; k < i; k++)
				A[j + k] = add(A[j + k] , MOD - A[j + k + i]);
}

inline void FWT_xor(int *A){
	for(register int i = 1; i < lim; i <<= 1)
		for(register int j = 0; j < lim; j += i << 1)
			for(register int k = 0; k < i; k++){
				const int L = A[j + k], R = A[j + k + i];
				A[j + k] = add(L, R), A[j + k + i] = add(L, MOD - R);
			}
}

inline void IFWT_xor(int *A){
	for(register int i = 1; i < lim; i <<= 1)
		for(register int j = 0; j < lim; j += i << 1)
			for(register int k = 0; k < i; k++){
				const int L = A[j + k], R = A[j + k + i];
				A[j + k] = add(L, R), A[j + k + i] = add(L, MOD - R);
				A[j + k] = mul(A[j + k], inv2), A[j + k + i] = mul(A[j + k + i], inv2);
			}
}

int main(){
	getint(n), lim = 1 << n;
	for(register int i = 0; i < lim; i++) getint(A[i]);
	for(register int i = 0; i < lim; i++) getint(B[i]);
	
	FWT_or(A), FWT_or(B);
	for(register int i = 0; i < lim; i++) C[i] = mul(A[i], B[i]);
	IFWT_or(A), IFWT_or(B), IFWT_or(C);
	for(register int i = 0; i < lim; i++) printf("%d ", C[i]); puts("");
	
	FWT_and(A), FWT_and(B);
	for(register int i = 0; i < lim; i++) C[i] = mul(A[i], B[i]);
	IFWT_and(A), IFWT_and(B), IFWT_and(C);
	for(register int i = 0; i < lim; i++) printf("%d ", C[i]); puts("");
	
	FWT_xor(A), FWT_xor(B);
	for(register int i = 0; i < lim; i++) C[i] = mul(A[i], B[i]);
	IFWT_xor(C);
	for(register int i = 0; i < lim; i++) printf("%d ", C[i]); puts("");
	return 0;
}