快速沃尔什变换（FWT）学习笔记

What 这是啥呀

\(~~~~\) 快速沃尔什变换也用于解决一些卷积问题，所不同的是它解决的卷积的下标一般由位运算代替加法，因此也可以用集合卷积来表示其所能解决的问题。

\(~~~~\) 才疏学浅，理解不深，仅能至此。

How 怎么做

\(~~~~\) 显然暴力卷积复杂度会飞天，所以我们想到用 \(\operatorname{FFT/NTT}\) 所使用的方式，把该多项式进行变换后使得对应项单独做乘法运算即可求得最后结果即可。

\(~~~~\) 换句话说我们要构造一种对于多项式的对应法则 \(\operatorname{FWT(A)}\)使得：\(\operatorname{FWT}(A\oplus B)=\operatorname{FWT}(A)\times\operatorname{FWT}(B)\)。其中 \(\oplus\) 即为所要求的卷积运算。这里的乘法单纯指对应项相乘。

\(~~~~\) 我们认为下面提到的多项式的长度 \(n\) 均为 \(2\) 的幂。

\(~~~~\) 在讲下面的部分前我们再引入两个符号：

• \(,\) ：表示连接前后两个多项式系数，如 \(\{1,1,4\},\{5,1,4\}=\{1,1,4,5,1,4\}\) 。（当然这个例子没有遵循长度必须为 \(2\) 的幂的限制）
• \(A_0,A_1\) ：分别表示多项式的前半部分和后半部分，如对于 \(A=\{1,1,4,5,1,4\}\) ，\(A_0=\{1,1,4\}\)，\(A_1=\{5,1,4\}\) （当然这个例子也没有遵循长度必须为 \(2\) 的幂的限制）

\(~~~~\) 引入了符号后考虑怎么构造呢？运用人类智慧不难得到：

或 FWT

\[\text{FWT}(A)= \left\{\begin{array}{l} \operatorname{FWT}(A_0),\operatorname{FWT}(A_0+A_1) && n>1 \\ A&&n=1 \end{array}\right. \]

与 FWT

\[\text{FWT}(A)= \left\{\begin{array}{l} \operatorname{FWT}(A_0+A_1),\operatorname{FWT}(A_1) && n>1 \\ A&&n=1 \end{array}\right. \]

异或 FWT

\[\text{FWT}(A)= \left\{\begin{array}{l} \operatorname{FWT}(A_0+A_1),\operatorname{FWT}(A_0-A_1) && n>1 \\ A&&n=1 \end{array}\right. \]

\(~~~~\) 当然我们还要还原，而显然这个逆运算非常好推，事实上把这当做解方程即可。

或 IFWT

\[\text{IFWT}(A)= \left\{\begin{array}{l} \operatorname{IFWT}(A_0),\operatorname{IFWT}(A_1-A_0) && n>1 \\ A&&n=1 \end{array}\right. \]

与 IFWT

\[\text{IFWT}(A)= \left\{\begin{array}{l} \operatorname{IFWT}(A_0-A_1),\operatorname{IFWT}(A_1) && n>1 \\ A&&n=1 \end{array}\right. \]

异或 IFWT

\[\text{IFWT}(A)= \left\{\begin{array}{l} \operatorname{IFWT}(\frac{A_0+A_1}{2}),\operatorname{IFWT}(\frac{A_0-A_1}{2}) && n>1 \\ A&&n=1 \end{array}\right. \]

Copy Paste 太爽了！

Why 为什么它是对的

\(~~~~\) 由于证明过程类似，我们只对或运算的正确性进行证明。

\(~~~~\) 归根结底也就是要证对于或运算：\(\text{FWT(A}\operatorname{or} \text{B)=FWT(A)}\times\text{FWT(B)}\) 。

\(~~~~\) 这一类证明一般使用数学归纳法，因此我们从底层 \(n=1\) 证起：

\[\operatorname{FWT}(A \operatorname{or} B)=A \times B=\operatorname{FWT}(A)\times \operatorname{FWT}(B) \]

\(~~~~\) 而当 \(n>1\) 时考虑在什么情况下或运算会分到后半部分，什么情况下会分到前半部分：

\[\operatorname{FWT}(A \operatorname{or} B) = \operatorname{FWT}[(A_0 \operatorname{or} B_0),(A_0\operatorname{or}B_1)+(A_1 \operatorname{or} B_0)+(A_1 \operatorname{or} B_1)]\\ \]

\(~~~~\) 由定义展开：

\[=\operatorname{FWT}[(A_0 \operatorname{or} B_0)],\operatorname{FWT}[(A_0 \operatorname{or} B_0)+(A_0\operatorname{or}B_1)+(A_1 \operatorname{or} B_0)+(A_1 \operatorname{or} B_1)] \]

\(~~~~\) 这里用到一个猜想：\(\operatorname{FWT(A+B)}=\operatorname{FWT}(A)+\operatorname{FWT}(B)\) ，稍后我们会证明它

\[=\operatorname{FWT}[(A_0 \operatorname{or} B_0)],\operatorname{FWT}[(A_0 \operatorname{or} B_0)]+\operatorname{FWT}[(A_0\operatorname{or}B_1)]+\operatorname{FWT}[(A_1 \operatorname{or} B_0)]+\operatorname{FWT}[(A_1 \operatorname{or} B_1)]\\ \]

\(~~~~\) 把它再用下层结论打开：

\[=[\operatorname{FWT}(A_0)\times \operatorname{FWT}(B_0)],[\operatorname{FWT}(A_0)\times \operatorname{FWT}(B_0)]+[\operatorname{FWT}(A_0)\times \operatorname{FWT}(B_1)]\\+[\operatorname{FWT}(A_1)\times \operatorname{FWT}(B_0)]+[\operatorname{FWT}(A_1)\times \operatorname{FWT}(B_1)] \]

\(~~~~\) 整理一下：

\[=[\operatorname{FWT}(A_0)\times \operatorname{FWT}(B_0)],\operatorname{FWT}(A_0+A_1)\times \operatorname{FWT}(B_0+B_1) \]

\(~~~~\) 不难注意到一个事实：\([\operatorname{FWT}(A)\times \operatorname{FWT(B)}],[\operatorname{FWT}(C)\times \operatorname{FWT}(D)]=[\operatorname{FWT}(A),\operatorname{FWT}(C)]\times [\operatorname{FWT}(B),\operatorname{FWT}(D)]\) 。

\(~~~~\) 故原式可改写为：

\[=[\operatorname{FWT}(A_0),\operatorname{FWT}(A_0+A_1)]\times [\operatorname{FWT}(B_0),\operatorname{FWT}(B_0+B_1)]\\ =\operatorname{FWT}(A)\times \operatorname{FWT}(B) \]

\(~~~~\) 故得证。

\(~~~~\) 但最后还得证我们的猜想：\(\operatorname{FWT(A+B)}=\operatorname{FWT}(A)+\operatorname{FWT}(B)\)

\(~~~~\) 仍然先证 \(n=1\) 的情况：

\[\operatorname{FWT}(A+B)=A+B=\operatorname{FWT}(A)+\operatorname{FWT}(B) \]

\(~~~~\) 然后 \(n>1\) ：

\[\operatorname{FWT}(A+B)=\operatorname{FWT}[(A+B)_0],\operatorname{FWT}[(A+B)_0+(A+B)_1]\\ =\operatorname{FWT}(A_0)+\operatorname{FWT}(B_0),\operatorname{FWT}(A_0)+\operatorname{FWT}(B_0)+\operatorname{FWT}(A_1)+\operatorname{FWT}(B_1) \]

\(~~~~\) 仍然用于上面事实类似的方法：

\[=[\operatorname{FWT}(A_0),\operatorname{FWT}(A_0)+\operatorname{FWT}(A_1)]+[\operatorname{FWT}(B_0),\operatorname{FWT}(B_0)+\operatorname{FWT}(B_1)]\\ =\operatorname{FWT}(A)+\operatorname{FWT}(B) \]

\(~~~~\) 至此或运算的正确性得证。

\(~~~~\) 与运算和异或运算类比可得。

Code

查看代码

#include <cstdio>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
int n; 
const int MOD=998244353;
inline ll Add(ll a,ll b){return (a+b)%MOD;}
inline ll Dec(ll a,ll b){return (a-b+MOD)%MOD;}
inline ll Mul(ll a,ll b){return 1ll*a*b%MOD;}
ll qpow(ll a,ll b)
{
	ll ret=1;
	while(b)
	{
		if(b&1) ret=ret*a%MOD;
		b>>=1;a=a*a%MOD;
	}
	return ret;
}
int a[500005],b[500005];
int A[500005],B[500005],C[500005];
void Copy(){for(int i=0;i<n;i++) A[i]=a[i],B[i]=b[i];}
void OR(int *S,int op)
{
	if(op==-1) op=MOD-1;
	for(int i=1;i<n;i<<=1)
		for(int j=0;j<n;j+=i<<1)
			for(int k=0;k<i;k++) S[i+j+k]=Add(S[i+j+k],Mul(S[j+k],op));
}
void AND(int *S,int op)
{
	if(op==-1) op=MOD-1;
	for(int i=1;i<n;i<<=1)
		for(int j=0;j<n;j+=i<<1)
			for(int k=0;k<i;k++) S[j+k]=Add(S[j+k],Mul(S[i+j+k],op));
}
void XOR(int *S,int op)
{
	if(op==-1) op=qpow(2,MOD-2);
	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 x=S[j+k],y=S[i+j+k];
				S[j+k]=Mul(op,Add(x,y)); S[i+j+k]=Mul(op,Dec(x,y));
			}
		}
	}
}
int main() {
	scanf("%d",&n); n=1<<n;
	for(int i=0;i<n;i++) scanf("%d",&a[i]);
	for(int i=0;i<n;i++) scanf("%d",&b[i]);
	Copy(); OR(A,1);  OR(B,1);  for(int i=0;i<n;i++) C[i]=Mul(A[i],B[i]); OR(C,-1);  for(int i=0;i<n;i++) printf("%d ",C[i]);puts("");
	Copy(); AND(A,1); AND(B,1); for(int i=0;i<n;i++) C[i]=Mul(A[i],B[i]); AND(C,-1); for(int i=0;i<n;i++) printf("%d ",C[i]);puts("");
	Copy(); XOR(A,1); XOR(B,1); for(int i=0;i<n;i++) C[i]=Mul(A[i],B[i]); XOR(C,-1); for(int i=0;i<n;i++) printf("%d ",C[i]);puts("");
	return 0;
}