FWT总结

学习笔记 题单

引入

一般的多项式乘法是这样子的:

$c_i=\sum_{i,j}a_j*b_k*[j+k==i]$

但是如果我们将这个乘法式子里面的+号变换一下变成其他的运算符号呢?

$c_i=\sum_{i,j}a_j*b_k*[j\oplus k==i]$

其中$\oplus$可以取$and,or,xor$

这个时候FFT和NTT就没有什么用了...

前人的智慧是无穷的!

考虑一个神奇的算法:FWT(快速沃尔什变化)

or卷积

先从最容易的or卷积下手.

我们考虑他给出的式子:

$c_i=\sum_{i,j}a_j*b_k*[i|j==k]$

我们将i,j按照二进制拆开,发现这其实相当于是一个状压dp?

然后就可以直接搞了(因为这个二进制有传递的效果.)

上面是废话...

考虑怎么求这个玩意:

用一个式子:

$FWT(A)=\begin{cases}(FWT(A_0),FWT(A_0+A_1)) & n\gt0 \\ A & n=0\end{cases}$

这个证明不会(真的菜)

然后只要把这个套进去就可以了(或还是比较简单)

然后就好了啊.qwq

and卷积

这个东西的话其实和or没有什么比较大的区别:

$FWT(A)=\begin{cases}(FWT(A_0+A_1),FWT(A_1)) & n\gt0 \\ A & n=0\end{cases}$

xor卷积

$FWT(A)=\begin{cases}(FWT(A_0)+FWT(A_1),FWT(A_0)-FWT(A_1)) & n>0\\A & n=0\end{cases}$

证明的坑以后会补的.

IFWT

考虑FFT我们怎么做的?

肯定是先把$FFT(C)=FFT(A)*FFT(B)$(这个是逐位乘)

然后再还原对吧.

所以FWT也需要还原.

然后既然怎么来的推出来了,怎么回去也就会了不是吗?

代码实现

namespace cpp1{
    int A[N],B[N],limit;
    void init(){
        limit=len;
        for(int i=0;i<limit;i++)A[i]=a[i];
        for(int i=0;i<limit;i++)B[i]=b[i];
    }
    void FMT(int *A,int limit,int opt){
        for(int i=1;i<limit;i<<=1)
            for(int j=0;j<limit;j++)
                if(i&j)
                    if(opt==1)A[j]=(A[j]+A[j^i])%Mod;
                    else A[j]=(A[j]+Mod-A[j^i])%Mod;
    }
    void solve(){
        FMT(A,limit,1);FMT(B,limit,1);
        for(int i=0;i<limit;i++)A[i]=(1ll*A[i]*B[i])%Mod;
        FMT(A,limit,-1);
        for(int i=0;i<limit;i++)printf("%d%c",A[i],i==limit-1?'\n':' ');
    }
}
namespace cpp2{
    int A[N],B[N],limit;
    void init(){
        limit=len;
        for(int i=0;i<limit;i++)A[i]=a[i];
        for(int i=0;i<limit;i++)B[i]=b[i];
    }
    void FWTand(int *a,int limit,int opt){
        for(int i=1;i<limit;i<<=1)
            for(int j=0,p=i<<1;j<limit;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]-a[i+j+k]+Mod)%Mod;
    }
    void solve(){
        FWTand(A,limit,1);FWTand(B,limit,1);
        for(int i=0;i<limit;i++)A[i]=(1ll*A[i]*B[i])%Mod;
        FWTand(A,limit,-1);
        for(int i=0;i<limit;i++)printf("%d%c",A[i],i==limit-1?'\n':' ');
    }
}
namespace cpp3{
    int A[N],B[N],limit,inv2=499122177;
    void init(){
        limit=len;
        for(int i=0;i<limit;i++)A[i]=a[i];
        for(int i=0;i<limit;i++)B[i]=b[i];
    }
    void FWTxor(int *a,int limit,int opt){
        for(int i=1;i<limit;i<<=1)
            for(int p=i<<1,j=0;j<limit;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;
                    }
                }
    }
    void solve(){
        FWTxor(A,limit,1);FWTxor(B,limit,1);
        for(int i=0;i<limit;i++)A[i]=(1ll*A[i]*B[i])%Mod;
        FWTxor(A,limit,-1);
        for(int i=0;i<limit;i++)printf("%d%c",A[i],i==limit-1?'\n':' ');
    }
}