(FWT)--快速沃尔什变化学习笔记
知识点
(FWT)就是求两个多项式的位运算卷积。类比(FFT)，(FFT)大多数求的卷积形式为(c_n=sumlimits_{i+j=n}a_i*b_j)的形式。而(FWT)则求的卷积形式为(c_n=sumlimits_{ioplus j=n})，如何做这个玩意呢，我们还是考虑分治。把它分成两个部分，一个部分是(A_0)，一部分是(A_1)，分别表示的是最高位为(0/1)，然后对于与卷积来说(f(A)=(f(A_0+A_1)，f(A_1)))，对于或卷积来说(f(A)=(f(A_0)，f(A_0+A_1)))，对于异或卷积来说(f(A)=(f(A_0+A_1)，f(A_0-A_1)))。不会证明。。这是比较重要的几点，然后这些都是正变化。而逆变化对于与和或来说就是把(+)换成(-)，但对于异或卷积来说，(f(A)=(f((A_0+A_1)/2，f((A_0-A_1)/2))。知道了这些就可以开始做题了。
例题
(1)，洛谷(4717)
(https://www.luogu.org/problemnew/show/P4717)
解题思路：
对，就是模板题！
(Code)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 1<<18;
const int MOD = 998244353;
const int INV = 499122177;
int limit,f[MAXN],g[MAXN],a[MAXN],b[MAXN],n;
inline int rd(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return f?x:-x;
}
inline int add(int x,int y){
int ret=x+y;while(ret>=MOD) ret-=MOD;while(ret<0) ret+=MOD;return ret;
}
void out(int x){
if(!x) return;out(x/10);putchar('0'+x%10);
}
inline void OUT(int x){
if(x<0) putchar('-');
if(x==0) putchar('0');
else out(x);putchar(' ');
}
inline void fwt1(int *f,int type){ //or
for(int mid=1;mid<limit;mid<<=1)
for(int j=0,len=mid<<1;j<limit;j+=len)
for(int k=j;k<mid+j;k++)
f[mid+k]=add(f[mid+k],type*f[k]);
}
inline void fwt2(int *f,int type){ //and
for(int mid=1;mid<limit;mid<<=1)
for(int j=0,len=mid<<1;j<limit;j+=len)
for(int k=j;k<mid+j;k++)
f[k]=add(f[k],type*f[k+mid]);
}
inline void fwt3(int *f,int type){ //xor
int x,y;
for(int mid=1;mid<limit;mid<<=1)
for(int j=0,len=mid<<1;j<limit;j+=len)
for(int k=j;k<mid+j;k++){
x=f[k];y=f[k+mid];
f[k]=add(x,y);f[k+mid]=add(x,-y);
if(type==-1) f[k]=(LL)f[k]*INV%MOD,f[k+mid]=(LL)f[k+mid]*INV%MOD;
}
}
int main(){
n=rd();limit=1<<n;
for(int i=0;i<limit;i++) a[i]=f[i]=rd();
for(int i=0;i<limit;i++) b[i]=g[i]=rd();
fwt1(f,1);fwt1(g,1);
for(int i=0;i<limit;i++) f[i]=(LL)f[i]*g[i]%MOD;
fwt1(f,-1);
for(int i=0;i<limit;i++) OUT(f[i]);putchar('
');
for(int i=0;i<limit;i++) f[i]=a[i];
for(int i=0;i<limit;i++) g[i]=b[i];
fwt2(f,1);fwt2(g,1);
for(int i=0;i<limit;i++) f[i]=(LL)f[i]*g[i]%MOD;
fwt2(f,-1);
for(int i=0;i<limit;i++) OUT(f[i]);putchar('
');
for(int i=0;i<limit;i++) f[i]=a[i];
for(int i=0;i<limit;i++) g[i]=b[i];
fwt3(f,1);fwt3(g,1);
for(int i=0;i<limit;i++) f[i]=(LL)f[i]*g[i]%MOD;
fwt3(f,-1);
for(int i=0;i<limit;i++) OUT(f[i]);
return 0;
}
(2)，(bzoj) (4589)
(https://www.lydsy.com/JudgeOnline/problem.php?id=4589)
解题思路：
博弈论(+ FWT)，首先(nim)游戏所有石子堆的异或和为(0)时先手必败。设(f_i)表示异或和为(i)时的情况，我们最后要求的是(f_0)。设(a_i)表示这堆石子能否为(i)，那么对于两堆石子来说(f_i=sumlimits_{jland k=i}a_j*a_k)，对于三堆石子来说(f_i'=sumlimits_{jland k=i}f_j*a_k)。这样就能发现规律了。首先我们先用(FWT)正变化一下，然后求一个(pow(a_i,n))，在逆变化回去。
(Code)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#define int long long
using namespace std;
const int MAXN = 50005;
const int MOD = 1e9+7;
const int INV = 500000004;
typedef long long LL;
int n,m,prime[MAXN],cnt,limit=1,now;
LL a[MAXN<<1];
bool vis[MAXN];
inline LL add(LL ret){
while(ret>=MOD) ret-=MOD;while(ret<0) ret+=MOD;return ret;
}
inline void fwt(LL *f,int type){
LL x,y;
for(int mid=1;mid<limit;mid<<=1)
for(int j=0,len=mid<<1;j<limit;j+=len)
for(int k=j;k<j+mid;k++){
x=f[k];y=f[k+mid];
f[k]=add(x+y);f[k+mid]=add(x-y);
if(type==-1) f[k]=f[k]*INV%MOD,f[k+mid]=f[k+mid]*INV%MOD;
}
}
inline LL fast_pow(LL x,int y){
LL ret=1;
for(;y;y>>=1){
if(y&1) ret=ret*x%MOD;
x=x*x%MOD;
}
return ret;
}
signed main(){
for(int i=2;i<=50000;i++){
if(!vis[i]) prime[++cnt]=i;
for(int j=1;j<=cnt && prime[j]*i<=50000;j++)
vis[i*prime[j]]=1;
}
while(~scanf("%lld%lld",&n,&m)){
if(n==1) {puts("0");continue;}
memset(a,0,sizeof(a));limit=1;now=0;
for(int i=1;i<=cnt;i++){
if(prime[i]<=m) a[prime[i]]=1;
else {now=prime[i-1];break;}
}if(!now) now=prime[cnt];
while(limit<=now) limit<<=1;
fwt(a,1);
for(int i=0;i<limit;i++) a[i]=fast_pow(a[i],n);
fwt(a,-1);printf("%lld
",a[0]);
}
return 0;
}
(3)，(cf) (662C)
(https://www.luogu.org/problemnew/show/CF662C)
解题思路：
状态压缩(+FWT)。首先要把每一列压成一个(0/1)串，这样就变成一个长度为(m)的数列。然后可以(2^n)枚举一下翻哪一行，再(O(m))的枚举一下列，让每一列先(xor)上外层枚举的状态，在取一个(min(1,0))加入答案。这样时间复杂度是(O(2^n*m))的，考虑优化。设(ans_s)为翻的行的状态为(s)时的最小值，(f_i)为刚开始(i)这个状态的个数，(g_i)表示(i)这个状态的(0/1)的最小值。那么(ans_s=sumlimits_{iland j=s} f_i*g_j)，然后(FWT)一下即可。
(Code)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN = 1<<21;
typedef long long LL;
inline int rd(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return f?x:-x;
}
int n,m,S[100005];
LL f[MAXN],g[MAXN],ans=1e18;
inline int min(int x,int y){
return x<y?x:y;
}
inline void fwt(LL *f,int type){
LL x,y;
for(int mid=1;mid<(1<<n);mid<<=1)
for(int j=0,len=mid<<1;j<1<<n;j+=len)
for(int k=j;k<j+mid;k++){
x=f[k];y=f[k+mid];
f[k]=x+y;f[k+mid]=x-y;
if(type==-1) f[k]/=2,f[k+mid]/=2;
}
}
int main(){
n=rd(),m=rd();char s[100005];
for(int i=1;i<=n;i++){
scanf("%s",s+1);
for(int j=1;j<=m;j++)
if(s[j]=='1') S[j]|=(1<<(i-1));
}
for(int i=1;i<=m;i++) f[S[i]]++;int cnt;
for(int i=0;i<(1<<n);i++){
cnt=__builtin_popcount(i);
g[i]=min(cnt,n-cnt);
}
fwt(f,1);fwt(g,1);
for(int i=0;i<(1<<n);i++) f[i]=f[i]*g[i];
fwt(f,-1);
for(int i=0;i<(1<<n);i++) ans=min(ans,f[i]);
printf("%lld
",ans);
return 0;
}