FWT 学习笔记

想尽量讲得本质一点。

首先有一个引出问题叫做 集合幂级数

其中，\(opt\) 是集合的并交补运算，而 \(i,j,k\) 也都是集合的意思

当我们把 \(i,j,k\) 看成二进制表示，那么集合中的每一个元素的选/不选对应二进制的 \(1/0\) ， \(opt\) 变成了 \(or,and,xor\) 的一种

所以问题变成了这样：给定两个长度为 \(2^n\) 的序列 \(a_i,b_i\) （不够长用 \(0\) 补全），求出一个序列 \(c\) ，满足 \(\forall i,c_i=\sum_{j \ opt\ k=i}a_jb_k\)

这个时候我们可以使用，FWT ，\(\text{Fast Walsh-Hadamard Transform}\) ，快速沃尔什变换。

FFT

发现 \(fwt\) 和 \(fft\) 的英文很像，所以我们考虑，类似的思路

关于 \(fft\) ，我们有一个经典思路是：（图源：pyb 的 ppt)

其中，我们能做到 \(O(n\log n)\) 的 \(DFT\) 的原因在于我们有两个重要操作叫做 奇偶分段 蝴蝶变换 ，也就是说我们把原来的东西进行分治的操作后可以 \(O(1)\) 的合并回去，\(O(n\log n)\) 的 \(IDFT\) 在于一个 \(w\) 的性质的应用，我们不妨尝试把这样的思想套进 FWT

记住上图！

FWT

现在我们有这样的目标：找到一种变换 \(FWT\) ，使得

其中，\(\times\) 表示对应位相乘，然后通过 \(FWT(C)\) 复原 \(C\)

显然，我们的 FWT 应该是对于原序列的一种线性组合，即某一项只是若干个原多项式中的若干项的若干倍的和

因为我们本来的 \(c_i\) 就是数个 \(a_jb_k\) 的和，而 FWT 是对应位相乘，如果其出现原多项式某几项的乘积，那么显然 GG

所以显然有的是 \(FWT(A+B)=FWT(A)+FWT(B)\)

这里不妨约定一些记号:

$ ?? = ??_?? ,?? = ??_?? , ?? = ??_?? $

$ ?? + ?? = ??_0 + ??_0, ??_1 + ??_1,\dots $

$ ?? ? ?? = ??_0 ? ??_0, ??_1 ? ??_1,\dots$

$ ??\oplus?? = \sum_{?????=0} ??_?? ? ??_?? , \sum_{?????=1} ??_?? ? ??_?? ,\dots$

默认所有的数列都有 \(2^n\) 项，即可以理解为集合元素个数有 \(??\) 个

$ ??_0$ 代表数列 \(??\) 的前 \(2^{???1}\) 项，即最高位（第一个）不选的所有集合，\(??_1\) 代表数列 \(??\) 中的后 \(2 ^{???1}\) ，即最高位（第一个）选的所有集合

FWTor

假设现在我们的 \(opt\) 就是 \(or\) ，下面简记 \(A|B=\sum_{j|k=i} a_jb_k\)

下面讲得可能有点小乱

FWT

总体想法是仿照 FFT ，考虑一个递归的形式构造出 FWT

显然，当 \(n=0\) 的时候，\(FWT(A)=A\)

下面讨论 \(n>0\) 的情况，我们首先考虑奇偶分段，假装我们已经知道了 \(FWT(A_0),FWT(A_1)\)

于是，一个粗略的 FWT 出现了： \(FWT(A)=Merge(FWT(A_0),FWT(A_1))\)

\(Merge\) 表示直接拼接，xjb 举一个例子：\(Merge(998,244)=998244\)

我们知道 \(FWT(C)\) 需要等于 \(FWT(A)\times FWT(B)\)

还知道 \(C_0=A_0B_0\) ,$ C_1=A_0B_1+A_1B_0+A_1 B_1$

发现上面那个显然不靠谱，我们对应位相乘后，只会得到 \(FWT(C_0)=FWT(A_0)FWT(B_0),FWT(C_1)=FWT(A_1)FWT(B_1)\) 这样一个错误。

也就是说后半部分还需要有 \(FWT(A_0)\) 的信息甩进去，所以：（这里不妨将 FWT 当成一个神秘的抽象函数）

（回顾 \(+\) 的记号：$ ?? + ?? = ??_0 + ??_0, ??_1 + ??_1,\dots $）

可是这样还是有问题呀，这样对应位相乘，好像会多一个 \(FWT(A_0)FWT(B_0)\) 项的贡献出现在 \(FWT(C_1)\) 中

但值得注意的是， \(FWT(C)\) 并不一定需要就是 \(C\) 了，我们不妨将这个问题交给 \(IFWT\) 处理，

至少我们这里保证了信息是完全的，并且符合我们心目中奇偶分段和蝴蝶变换的要求

也就是说像这样给出来后，IFWT 有操作空间，并且 FWT 时间的确是 \(n\log n\)

当然，我们还需要保证 \(FWT(A)\times FWT(B)=FWT(C)\)

这里采用类似数学归纳法的方式证明，思路来自 pyb 的 ppt ，

即假设已知 \(FWT(A_0)\times FWT(B_0)=FWT(C_0),FWT(A_0)FWT(B_1)+FWT(A_1)FWT(B_0),FWT(A_1)FWT(B_1)=FWT(C_1)\) ，那么

小心 \(Merge\) 的括号打的位置

第一个等号：按 FWT 定义展开

第二个等号：按 \(\times\) 定义对应位相乘

第三个等号：利用归纳法得到的结论

第四个等号：把 \(A_0B_0\) 理解成 \(A^{\prime}_0\) , \(A_0B_1+A_1B_0+A_1B_1\) 理解成 \(A^{\prime}_1\)

第五个等号：前文在定义 Merge 的后面一点点所述：

还知道 \(C_0=A_0B_0\) ,$ C_1=A_0B_1+A_1B_0+A_1 B_1$

所以我们归纳证明了 \(FWT(A)\times FWT(B)=FWT(C)\)

IFWT

（小剧场）

FWT: 至高无上的 IFWT ！吾交给汝一个使命：干掉 $FWT(A) \times FWT(B) $ 之后出现在 \(FWT(C_1)\) 中的 \(FWT(A_0B_0)\) 项！主不需要它！

IFWT：（心里mmp：彩笔 FWT）哈哈哈！看我容斥！

（突然发现自己好智障）

直接给出来：

其中传入的 \(A\) 是经历了 \(FWT\) 的产物，小证一手：

\(FWT(A)\times FWT(B)=FWT(C_0)+FWT(C_0+C_1)\)

所以：

\(IFWT(FWT(C_0)+FWT(C_0+C_1))=Merge(IFWT(FWT(C_0)),IFWT(C_0+C_1-C_0))=Merge(IFWT(FWT(C_0)),IFWT(FWT(C_1)))=C\)

FWT 的本质

我们考虑 FWT 的代码怎么写，这里再嫖一张 pyb 的 ppt

发现 \(FWT\) 做的事情就是不断地让箭头的起点加到箭头的终点，按照红绿蓝的顺序一层一层地加，可以有代码：

void FWT(ll *A){
	for(int i=2;i<=N;i<<=1)         //i 线段长度
		for(int p=i>>1,j=0;j

void IFWT(ll *A){
	for(int i=2;i<=N;i<<=1)         
		for(int p=i>>1,j=0;j

void FWT(ll *A,int op){
	for(int i=2;i<=N;i<<=1)         //i 线段长度
		for(int p=i>>1,j=0;j

void FWT(ll *A,int opt){
	for(int i=2;i<=N;i<<=1)
		for(int p=i>>1,j=0;j

void fwtxor(int *f,int op){
    for(int i=2;i<=len;i<<=1)
        for(int p=i>>1,j=0;j

#include
#define int long long
using namespace std;
const int N = (1<<21);
const int M = 1e5+5;

char s[25][M];
int a[N],b[N];
int n,m,ans=1e18;

void fwtxor(int *f,int op){
    for(int i=2;i<=(1<>1,j=0;j<(1<

#include
using namespace std;
const int N = 1<<21;
const int mod = 1e9+9;

int read(){
	int s=0,w=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
	while(isdigit(ch))s=s*10+ch-'0',ch=getchar();
	return s*w;
}

int a[21][N],b[21][N],c[21][N];
int n,len;

void fwt(int *f,int op){
	for(int i=2;i<=len;i<<=1)
		for(int p=i>>1,j=0;j

#include
#define int long long
#define ppc(x) __builtin_popcount(x)
using namespace std;
const int mod = 998244353;
const int N = 22;

char buf[1<<23],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
int read(){
    int s=0,w=1; char ch=getchar();  
    while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
    while(isdigit(ch))s=s*10+(ch^48),ch=getchar();
    return s*w;
}

int u[N*N],v[N*N],w[N],fa[N],deg[N],inv[(1<>=1;
    }
    return res;
}
void preparation(){
    for(int i=0,sum,cnt,flag;sum=cnt=flag=0,i<(1<>1;j<(1<