【学习笔鸡】快速沃尔什变换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_{jsubseteq i}C[j]
]
那么证明一下：
[egin{array}
&C'[i]&=sum_{jsubseteq i} C[j]
\
&=sum_{jsubseteq i}sum_{p|k=j} A[p]B[k]
\
&=sum_{psubseteq i,ksubseteq i} A[p]B[k]
\
&=sum_{psubseteq i} A[p]sum_{ksubseteq 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)=
egin{cases}
FWT(A_0),FWT(A_1+A_0) & k>0
\
A & k=0
end{cases}
]
逗号表示依次连接。
复杂度(T(n)=2T(n/2)+T(n)=O(nlog n))，而一般来说(n=2^m)那么就是(O(m2^m))
考虑(IFWT)
照猫画虎即可
[IFWT(A')=
egin{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{isubseteq j} C[j])，至于为什么构造，这个(j&k=i)可以看做(i)是(j,k)的子集。
同样有
[FWT(C)=FWT(A)*FWT(B)
]
证明:
[egin{array}
&C'[i]&=sum_{isubseteq j} C[j]
\
&= sum_{isubseteq j} sum_{k&p=j}A[k]B[p]
\
&= sum_{isubseteq k,isubseteq p}A[k]B[p]
\
&= sum_{isubseteq k}A[k]sum_{isubseteq p}B[p]
\
&=A'[i]B'[i]
end{array}
]
同样地
[FWT(A)=
egin{cases}
FWT(A_0+A_1),FWT(A_1)&k>0
\
A&k=0
end{cases}
]
同样的(T(n)=O(m2^m))
同样地
[IFWT(A')=
egin{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_{joplus k=i}A[j]B[k]
]
这里(FWT(X))貌似没有很直观的意义了，推式子的话其实也能理解
[FWT(C)=FWT(A)*FWT(B)
]
这里记录一个符号(Aoplus B=C)
那么
(C=Aoplus B)
拆成前后两半
[C_0=A_0oplus B_0+A_1oplus B_1
\
C_1=A_0oplus B_1+A_1oplus B_0
]
令
[X_0=(A_0+A_1)oplus (B_0+B_1)
\
X_1=(A_0-A_1)oplus (B_0-B_1)
]
然后?
[C_0={X_0+X_1over 2}
\
C_1={X_0-X_1 over 2}
]
但是好像学这个无法和各路大佬进行交流，并且我好像并没有学会，那么...
[FWT(A)=egin{cases}(FWT(A_0)+FWT(A_1),FWT(A_0)-FWT(A_1)) & n>0\A & n=0end{cases}
]
用循环实现的技巧和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('
');
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('
');
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('
');
return 0;
}