【学习笔鸡】快速沃尔什变换FWT

【学习笔鸡】快速沃尔什变换FWT

OR的FWT

快速解决:
\[C[i]=\sum_{j|k=i} A[j]B[k]\]
FWT使得我们
\[FWT(C)=FWT(A)*FWT(B)\]
其中\(*\)是点积，就是对应位置加起来。

而对于\(orFWT\)，
\[C'[i]=FWT(C)[i]=\sum_{j\subseteq i}C[j]\]
那么证明一下：
\[\begin{array}&C'[i]&=\sum_{j\subseteq i} C[j]\\&=\sum_{j\subseteq i}\sum_{p|k=j} A[p]B[k]\\&=\sum_{p\subseteq i,k\subseteq i} A[p]B[k]\\&=\sum_{p\subseteq i} A[p]\sum_{k\subseteq i}B[k]\\&=A'[i]B'[i]\end{array}\]
考虑\(A\)和\(A'\)的关系，其中\(A_0,A_1\)分别代表\(A\)的前\(2^{k-1}\)和后这么多项(下标都从0开始)。他们的差别是\(2^{k-1}\)位上的不同。其他相似。
\[FWT(A)=\begin{cases}FWT(A_0),FWT(A_1+A_0) & k>0\\A & k=0\end{cases}\]
逗号表示依次连接。

复杂度\(T(n)=2T(n/2)+T(n)=O(n\log n)\)，而一般来说\(n=2^m\)那么就是\(O(m2^m)\)

考虑\(IFWT\)

照猫画虎即可
\[IFWT(A')=\begin{cases}IFWT(A'_0),IFWT(A'_1-A'_0) & k>0\\A' & k=0\end{cases}\]
代码

inline void FWT_OR(int*a,const int&tag,const int&len){
    for(int t=1;t<len;t<<=1)
        for(int i=0;i<len;i+=t<<1)
            for(int k=0;k<t;++k)
                a[t+i+k]=(a[t+i+k]+a[t+i]*tag+mod)%mod;
}

AND的FWT

同样地，快速解决
\[C[i]=\sum_{j\& k=i}A[j]B[k]\]
可以构造\(C'[i]=FWT(C)[i]=\sum_\limits{i\subseteq j} C[j]\)，至于为什么构造，这个\(j\&k=i\)可以看做\(i\)是\(j,k\)的子集。

同样有
\[FWT(C)=FWT(A)*FWT(B)\]
证明:
\[\begin{array}&C'[i]&=\sum_{i\subseteq j} C[j]\\&= \sum_{i\subseteq j} \sum_{k\&p=j}A[k]B[p]\\&= \sum_{i\subseteq k,i\subseteq p}A[k]B[p]\\&= \sum_{i\subseteq k}A[k]\sum_{i\subseteq p}B[p]\\&=A'[i]B'[i]\end{array}\]
同样地
\[FWT(A)=\begin{cases}FWT(A_0+A_1),FWT(A_1)&k>0\\A&k=0\end{cases}\]
同样的\(T(n)=O(m2^m)\)

同样地
\[IFWT(A')=\begin{cases}IFWT(A'_0-A'_1),IFWT(A_1) &k>0\\A'&k=0\end{cases}\]
同样地

inline void FWT_AND(int*a,const int&tag,const int&len){
    for(int t=1;t<len;t<<=1)
        for(int i=0;i<len;i+=t<<1)
            for(int k=0;k<t;++k)
                a[t+i]=(a[t+i]+a[t+i+k]*tag+mod)%mod;
}

XOR的FWT

也是快速解决
\[C[i]=\sum_{j\oplus k=i}A[j]B[k]\]

这里\(FWT(X)\)貌似没有很直观的意义了，推式子的话其实也能理解
\[FWT(C)=FWT(A)*FWT(B)\]
这里记录一个符号\(A\oplus B=C\)

那么

\(C=A\oplus B\)

拆成前后两半
\[C_0=A_0\oplus B_0+A_1\oplus B_1\\C_1=A_0\oplus B_1+A_1\oplus B_0\]
令
\[X_0=(A_0+A_1)\oplus (B_0+B_1)\\X_1=(A_0-A_1)\oplus (B_0-B_1)\]
那么，由于\(<+,\oplus>\)是满足分配率的
\[C_0={X_0+X_1\over 2}\\C_1={X_0-X_1 \over 2}\]
​

但是好像学这个无法和各路大佬进行交流，并且我好像并没有学会，那么...
\[FWT(A)=\begin{cases}(FWT(A_0)+FWT(A_1),FWT(A_0)-FWT(A_1)) & n>0\\A & n=0\end{cases}\]
证明：
\[\begin{aligned} FWT(A\oplus B)=&(FWT(A\oplus B)_0+FWT(A\oplus B)_1,FWT(A\oplus B)_0-FWT(A\oplus B)_1)\\ =&(FWT(A_0\oplus B_0+A_1\oplus B_1+A_1\oplus B_0+A_0\oplus B_1)\\&,FWT(A_0\oplus B_0+A_1\oplus B_1-A_1\oplus B_0-A_0\oplus B_1))\\ =&((FWT(A_0)+FWT(A_1))\times(FWT(B_0)+FWT(B_1))\\ &,(FWT(A_0)-FWT(A_1))\times(FWT(B_0)-FWT(B_1))\\ =&(FWT(A_0+A_1)\times(B_0+B_1),FWT(A_0-A_1)\times FWT(B_0-B_1))\\ =&(FWT(A_0+A_1),FWT(A_0-A_1))\times(FWT(B_0+B_1),FWT(B_0-B_1))\\ =&FWT(A)\times FWT(B)\end{aligned}\]

用循环实现的技巧和NTT一致，控制长度，控制第几段，控制段内的循环变量

//@winlere
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;  typedef long long ll;
inline int qr(){
    int ret=0,f=0,c=getchar();
    while(!isdigit(c))f|=c==45,c=getchar();
    while(isdigit(c)) ret=ret*10+c-48,c=getchar();
    return f?-ret:ret;
}
const int maxn=1<<18|1;
const int mod=998244353;

inline void FWT_OR(int*a,const int&len,const int&tag){
    for(int t=1;t<len;t<<=1)
        for(int i=0;i<len;i+=t<<1)
            for(int k=0;k<t;++k)
                a[t+i+k]=(0ll+a[t+i+k]+a[i+k]*tag+mod)%mod;
}

inline void FWT_AND(int*a,const int&len,const int&tag){
    for(int t=1;t<len;t<<=1)
        for(int i=0;i<len;i+=t<<1)
            for(int k=0;k<t;++k)
                a[i+k]=(0ll+a[i+k]+a[t+i+k]*tag+mod)%mod;
}

inline void FWT_XOR(int*a,const int&len,const int&tag){
    int opt=tag==1?1:((mod+1)>>1);
    for(int t=1;t<len;t<<=1)
        for(int i=0;i<len;i+=t<<1)
            for(int k=0;k<t;++k){
                int t0=a[i+k],t1=a[i+k+t];
                if(tag==1) a[i+k]=(t0+t1)%mod,a[i+k+t]=(t0-t1+mod)%mod;
                else a[i+k]=1ll*(t0+t1)%mod*opt%mod,a[i+k+t]=1ll*(t0-t1+mod)%mod*opt%mod;
            }
}

int n,k;
int a[maxn],b[maxn],c[maxn];
int A[maxn],B[maxn];

int main(){
#ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    n=qr();
    for(int t=0;t<1<<n;++t) a[t]=qr();
    for(int t=0;t<1<<n;++t) b[t]=qr();
    size_t s=(1<<n)*4;

    memcpy(A,a,s); memcpy(B,b,s);
    FWT_OR(A,1<<n,1); FWT_OR(B,1<<n,1);
    for(int t=0;t<1<<n;++t) c[t]=1ll*A[t]*B[t]%mod;
    FWT_OR(c,1<<n,-1);
    for(int t=0;t<1<<n;++t) printf("%d ",c[t]);
    putchar('\n');

    memcpy(A,a,s); memcpy(B,b,s);
    FWT_AND(A,1<<n,1); FWT_AND(B,1<<n,1);
    for(int t=0;t<1<<n;++t) c[t]=1ll*A[t]*B[t]%mod;
    FWT_AND(c,1<<n,-1);
    for(int t=0;t<1<<n;++t) printf("%d ",c[t]);
    putchar('\n');

    memcpy(A,a,s); memcpy(B,b,s);
    FWT_XOR(A,1<<n,1); FWT_XOR(B,1<<n,1);
    for(int t=0;t<1<<n;++t) c[t]=1ll*A[t]*B[t]%mod;
    FWT_XOR(c,1<<n,-1);
    for(int t=0;t<1<<n;++t) printf("%d ",c[t]);
    putchar('\n');

    return 0;
}