(转载)快速沃尔什变换(FWT) (知识整理+板子总结)

小衣同学

已于 2024-12-30 10:55:41 修改

阅读量916

点赞数 1

分类专栏：知识点总结文章标签：知识点总结快速沃尔什变换 FWT

于 2019-03-02 17:04:30 首次发布

本文链接：https://blog.csdn.net/Code92007/article/details/88077549

版权

知识点总结专栏收录该内容

90 篇文章

订阅专栏

思路来源

快速沃尔什变换(FWT) 学习笔记_fwt xor-CSDN博客

FWT快速沃尔什变换学习笔记 - 小蒟蒻yyb - 博客园（含and、or、xor具体证明过程）

强力安利思路来源博主的博客，翻了好几个都看不懂，这两位比较清晰……

再补充一个：

【学习笔记】FWT，子集卷积-CSDN博客

用途

$c_{k}=\sum_{i\bigotimes j==k}a_{i}*b_{j},1<=i,j,k<=n$ ，

a数组如果在第i位为1，b数组在第j位为1，

那么卷积c数组在对应第k位为1

$\bigotimes$ 在这里可以是集合的与(and)，或(or)，异或(xor)

概念

FWT与FFT思想类似，通过一种转换，

把向量A和B分别加密成和其等长的向量AA和BB，

加密后的向量可以直接执行向量一对一的乘法，

即(x1,y1,z1)*(x2,y2,z2)==(x1*x2,y1*y2,z1*z2)这种，拓展到高维，

然后得到向量CC(x1*x2,y1*y2,z1*z2)，CC再解密，即得向量C

由于要求C与向量A和向量B的卷积相等，所以如何构造加密方式是一种问题

这里用@表示卷积运算，+表示数字的加法运算，∗表示数字的乘法运算。

设A，B为一个长为 $2^{k}$ 的向量，如果A,B不足 $2^{k}$ ，需要可以用0补齐，

设C=A@B，C也是一个 $2^{k}$ 的向量。

设tf(A)是对A做一次FWT的结果，结果也是一个 $2^{k}$ 的向量，

如果可以做FWT，需要满足的条件是：

tf(C)=tf(A)∗tf(B)，其中上面的*表示两个向量对应为相乘。

对于异或的运算来说

①当k=0，tf(A)=A

②当k>0时，tf(A)=(tf(A0)+tf(A1),tf(A0)−tf(A1))

其中A0表示向量A的前 $2^{k-1}$ 维，A1表示向量A的后 $2^{k-1}$ 维，

tf(A0)+tf(A1)和tf(A0)−tf(A1)是一个 $2^{k-1}$ 的向量，

而(tf(A0)+tf(A1),tf(A0)−tf(A1))就表示把二者连接起来，

成为一个 $2^{k}$ 的向量，是一个递归分治的过程。

下证在异或条件下，有tf(C)=tf(A)∗tf(B)

（以下k，都是指向量长度为 $2^{k}$ ）

引理：tf(A+B)=tf(A)+tf(B)

证明：

①k=0时，tf(A+B)=A+B=tf(A)+tf(B)，成立

②k>0时，设k-1时成立，

则tf(A+B)=(tf(A0+B0)+tf(A1+B1),tf(A0+B0)−tf(A1+B1))

由A0+B0 和A1+B1长度为 $2^{k-1}$ ，

有tf(A0+B0)=tf(A0)+tf(B0)，tf(A1+B1)=tf(A1)+tf(B1)成立

故有，

tf(A+B)

=(tf(A0)+tf(B0)+tf(A1)+tf(B1),tf(A0)+tf(B0)−tf(A1)−tf(B1))

=(tf(A0)+tf(A1),tf(A0)−tf(A1))+(tf(B0)+tf(B1),tf(B0)−tf(B1))

=tf(A)+tf(B)，成立，

数学归纳法知引理tf(A+B)=tf(A)+tf(B)成立

下证tf(C)=tf(A)∗tf(B)成立

证明：

①当k=0时，tf(C)=C=A∗B=tf(A)∗tf(B)

②当k>0时，设k-1时成立，

由tf(A)=(tf(A0)+tf(A1),tf(A0)−tf(A1))，tf(B)=(tf(B0)+tf(B1),tf(B0)−tf(B1))

tf(A)∗tf(B)

=((tf(A0)+tf(A1))∗(tf(B0)+tf(B1)),(tf(A0)−tf(A1))∗(tf(B0)−tf(B1))（将括号展开）

=(tf(A0)∗tf(B0)+tf(A0)∗tf(B1)+tf(A1)∗tf(B0)+tf(A1)∗tf(B1),tf(A0)∗tf(B0)−tf(A0)∗tf(B1)−tf(A1)∗tf(B0)+tf(A1)∗tf(B1))

由tf(A0)∗tf(B0)长度为 $2^{k-1}$ ，有tf(A0)∗tf(B0)=tf(A0@B0)

故原式=(tf(A0@B0)+tf(A1@B1)+tf(A0@B1)+tf(A1@B0)，tf(A0@B0)+tf(A1@B1)−tf(A0@B1)−tf(A1@B0))

由异或每位都是独立的，根据最高位是0还是1，把A和B分别拆成了两部分。

所以C=(C0,C1)=(A0∗B0+A1∗B1,A0∗B1+A1∗B0)

C0=A0∗B0+A1∗B1表示当A、B最高位同为0或同为1时，异或结果为0

同理，C1=A0∗B1+A1∗B0表示当A、B最高位有且仅有一个1时，异或结果为1

tf(C)=tf(C0,C1)

=tf(A0@B0+A1@B1,A0@B1+A1@B0)

=(tf(A0@B0+A1@B1)+tf(A0@B1+A1@B0),tf(A0@B0+A1@B1)−tf(A0@B1+A1∗B0))

=(tf(A0@B0)+tf(A1@B1)+tf(A0@B1)+tf(A1@B0),tf(A0@B0)+tf(A1@B1)−tf(A0@B1)−tf(A1@B0))

=(tf(A0)∗tf(B0)+tf(A0)∗tf(B1)+tf(A1)∗tf(B0)+tf(A1)∗tf(B1),tf(A0)∗tf(B0)−tf(A0)∗tf(B1)−tf(A1)∗tf(B0)+tf(A1)∗tf(B1))

=((tf(A0)+tf(A1))∗(tf(B0)+tf(B1)),(tf(A0)−tf(A1))∗(tf(B0)−tf(B1))

=tf(A)*tf(B)，得证

tf函数得证，其逆函数ntf证明与其类似，

~~麻麻我再也不想看证明了~~

下面不加证明地给出三种运算的tf函数和ntf函数：

异或（Xor）

$tf(A)=(tf(A_{0})+tf(A_{1}),tf(A_{0})-tf(A_{1}))$

$utf(A)=(utf(\tfrac{A_{0}+A_{1}}{2}),utf(\tfrac{A_{0}-A_{1}}{2}))$
与（And）

$tf(A)=(tf(A_{0})+tf(A_{1}),tf(A_{1}))$

$utf(A)=(utf(A_{0})-utf(A_{1}),utf(A_{1}))$

或（Or）

$tf(A)=(tf(A_{0}),tf(A_{1})+tf(A_{0})))$

$utf(A)=(utf(A_{0}),utf(A_{1})-utf(A_{0})))$

板子1

//当⊕是^, &, |等某种位运算时，即是FWT快速沃尔什变换。
//FWT时，数组长度需要是2的整数次幂，不足补0。
//快速沃尔什变换
//防溢出可mod 1e9+7，则除以2的时候乘2的逆元。
//FWT后，相乘，UFWT回去即可 
void FWT(int a[],int n)  
{  
    for(int d=1;d<n;d<<=1)//i为半段区间的长度  
        for(int m=d<<1,i=0;i<n;i+=m)//i为整段区间的首位置，m为整段区间的长度  
            for(int j=0;j<d;j++)//j为在半段区间中的偏移量
            {  
                int x=a[i+j],y=a[i+j+d];  
                a[i+j]=(x+y)%mod,a[i+j+d]=(x-y+mod)%mod;  
                //xor:a[i+j]=x+y,a[i+j+d]=(x-y+mod)%mod;  
                //and:a[i+j]=x+y;  
                //or:a[i+j+d]=x+y;  
            }  
}  

void UFWT(int a[],int n)  
{  
    for(int d=1;d<n;d<<=1)  
        for(int m=d<<1,i=0;i<n;i+=m)  
            for(int j=0;j<d;j++)  
            {  
                int x=a[i+j],y=a[i+j+d];  
                a[i+j]=1LL*(x+y)*rev%mod,a[i+j+d]=(1LL*(x-y)*rev%mod+mod)%mod; 
                //rev表示2在模mod下的逆元 
                //xor:a[i+j]=(x+y)/2,a[i+j+d]=(x-y)/2;  
                //and:a[i+j]=x-y;  
                //or:a[i+j+d]=y-x;  
            }  
}  
void solve(int a[],int b[],int n)  
{  
    FWT(a,n);//对a加密  
    FWT(b,n);//对b加密
    for(int i=0;i<n;i++) a[i]=1LL*a[i]*b[i]%mod;//直接向量点乘  
    UFWT(a,n);//对点乘结果解密  
}

板子2（来自yyb巨神的博客园，长得更像FFT）

//inv2是mod意义下2的逆元,inv2=(mod+1)/2
void FWT_or(int *a,int opt)
{
    for(int i=1;i<N;i<<=1)
        for(int p=i<<1,j=0;j<N;j+=p)
            for(int k=0;k<i;++k)
                if(opt==1)a[i+j+k]=(a[j+k]+a[i+j+k])%mod;
                else a[i+j+k]=(a[i+j+k]+mod-a[j+k])%mod;
}
void FWT_and(int *a,int opt)
{
    for(int i=1;i<N;i<<=1)
        for(int p=i<<1,j=0;j<N;j+=p)
            for(int k=0;k<i;++k)
                if(opt==1)a[j+k]=(a[j+k]+a[i+j+k])%mod;
                else a[j+k]=(a[j+k]+mod-a[i+j+k])%mod;
}
void FWT_xor(int *a,int opt)
{
    for(int i=1;i<N;i<<=1)
        for(int p=i<<1,j=0;j<N;j+=p)
            for(int k=0;k<i;++k)
            {
                int X=a[j+k],Y=a[i+j+k];
                a[j+k]=(X+Y)%mod;a[i+j+k]=(X+mod-Y)%mod;
                if(opt==-1)a[j+k]=1ll*a[j+k]*inv2%mod,a[i+j+k]=1ll*a[i+j+k]*inv2%mod;
            }
}
int main()
{
	FWT_or(a,1);
	FWT_or(b,1);
	for(int i=0;i<n;++i)
        a[i]=1LL*a[i]*b[i]%mod;
	FWT_or(a,-1);
	return 0; 
}

子集卷积

如果想让cnt[i]的数恰好是j和k卷积的结果，其中j和k二进制位不交

那么控制卷积时恰好是cnt[j]+cnt[k]=cnt[i]的数放在一起卷积，并且只过滤保留那些cnt[i]=j的位置j

板子


	int n = readint(); cnt[0] = -1;
	for(int i=0; i<(1<<n); ++i){
		cnt[i] = cnt[i-(i&-i)]+1;
		a[cnt[i]][i] = readint();
	}
	for(int i=0; i<(1<<n); ++i)
		b[cnt[i]][i] = readint();
	for(int i=0; i<=n; ++i)
		FWT(a[i],n,1), FWT(b[i],n,1);
	for(int i=0; i<=n; ++i){
		memset(c,0,(1<<n)<<2);
		for(int j=0; j<=i; ++j)
		for(int k=0; k<(1<<n); ++k)
			c[k] = (c[k]+1ll*a[j][k]*b[i-j][k])%Mod;
		FWT(c,n,-1); // get all result
		for(int j=0; j<(1<<n); ++j)
			if(cnt[j] == i) res[j] = c[j];
	}