题解 P4717 【【模板】 快速沃尔什变换】
Great_Influence
2018-06-25 09:19:35
模板，没什么好说的。
$FWT$和$FMT$都是解决子集变换的优秀算法。其中$FMT$只能够解决子集或，而$FWT$根据不同的核心代码可以解决$and,or,xor$等不同算法。$FMT$的代码更加贴近$or$的数学证明，而$FWT$代码与$FFT$相似便于背诵。
$FWT$的核心代码(之前式子写错了都没人说一声啊):
$FWTor$:
$$X[i+k+len/2]+=X[i+k]$$
$IFWTor$:
$$X[i+k+len/2]-=X[i+k]$$
$FWTand$:
$$X[i+k]+=X[i+k+len/2]$$
$IFWTand$:
$$X[i+k]-=X[i+k+len/2]$$
$FWTxor$:
$$X[i+k]=X[i+k]+X[i+k+len/2]$$,
$$X[i+k+len/2]=X[i+k]-X[i+k+len/2]$$
$IFWTxor$:
$$X[i+k]=\frac{X[i+k]+X[i+k+len/2]}{2}$$,
$$X[i+k+len/2]=\frac{X[i+k]-X[i+k+len/2]}{2}$$
~~是不是很好背啊~~
代码:
```cpp
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#define Rep(i,a,b) for(register int i=(a),i##end=(b);i<=i##end;++i)
#define Repe(i,a,b) for(register int i=(a),i##end=(b);i>=i##end;--i)
#define For(i,a,b) for(i=(a),i<=(b);++i)
#define Forward(i,a,b) for(i=(a),i>=(b);--i)
template<typename T>inline void read(T &x)
{
T f=1;x=0;char c;
for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-1;
for(;isdigit(c);c=getchar())x=x*10+(c^48);
x*=f;
}
inline void write(int u,char ed='\n')
{
if(!u){putchar(48);putchar(ed);return;}
static int sta[43],tp;
for(tp=0;u;u/=10)sta[++tp]=u%10;
for(;tp;putchar(sta[tp--]^48));
putchar(ed);
}
using namespace std;
const int MAXN=(1<<17)+5;
typedef long long ll;
static int n,Len=1<<17;
static int S[MAXN],Fi[MAXN],bit[MAXN];
const int mod=998244353;
inline int ad(int u,int v){return (u+=v)>=mod?u-mod:u;}
inline void predone(int lim)
{
Fi[0]=0;Fi[1]=1;
Rep(i,1,lim)bit[i]=bit[i>>1]+(i&1);
}
inline void FMT(int *a)//快速莫比乌斯变换
{
for(register int z=1;z<Len;z<<=1)
Rep(j,0,Len-1)if(z&j)a[j]=ad(a[j],a[j^z]);
}
inline void IFMT(int *a)//快速莫比乌斯反演
{
for(register int z=1;z<Len;z<<=1)
Rep(j,0,Len-1)if(z&j)a[j]=ad(a[j],mod-a[j^z]);
}
inline void FWTand(int *a)//快速沃尔什变换及其反演
{
for(register int i=2,ii=1;i<=Len;i<<=1,ii<<=1)
for(register int j=0;j<Len;j+=i)
for(register int k=0;k<ii;++k)
a[j+k]=ad(a[j+k],a[j+k+ii]);
}
inline void IFWTand(int *a)
{
for(register int i=2,ii=1;i<=Len;i<<=1,ii<<=1)
for(register int j=0;j<Len;j+=i)
for(register int k=0;k<ii;++k)
a[j+k]=ad(a[j+k],mod-a[j+k+ii]);
}
inline void FWTxor(int *a)
{
static int t;
for(register int i=2,ii=1;i<=Len;i<<=1,ii<<=1)
for(register int j=0;j<Len;j+=i)
for(register int k=0;k<ii;++k)
{
t=a[j+k];
a[j+k]=ad(t,a[j+k+ii]);
a[j+k+ii]=ad(t,mod-a[j+k+ii]);
}
}
inline int div2(int x){return x&1?(mod+x)/2:x/2;}
inline void IFWTxor(int *a)
{
static int t;
for(register int i=2,ii=1;i<=Len;i<<=1,ii<<=1)
for(register int j=0;j<Len;j+=i)
for(register int k=0;k<ii;++k)
{
t=a[j+k];
a[j+k]=div2(ad(t,a[j+k+ii]));
a[j+k+ii]=div2(ad(t,mod-a[j+k+ii]));
}
}
static int A[MAXN],B[MAXN],C[MAXN];
inline void init()
{
read(n);Len=1<<n;
Rep(i,0,Len-1)read(A[i]);
Rep(i,0,Len-1)read(B[i]);
}
inline void solve()
{
FMT(A);FMT(B);
Rep(i,0,Len-1)C[i]=(unsigned long long)A[i]*B[i]%mod;
IFMT(A);IFMT(B);IFMT(C);
Rep(i,0,Len-1)write(C[i],' ');
putchar('\n');
FWTand(A);FWTand(B);
Rep(i,0,Len-1)C[i]=(unsigned long long)A[i]*B[i]%mod;
IFWTand(A);IFWTand(B);IFWTand(C);
Rep(i,0,Len-1)write(C[i],' ');
putchar('\n');
FWTxor(A);FWTxor(B);
Rep(i,0,Len-1)C[i]=(unsigned long long)A[i]*B[i]%mod;
IFWTxor(C);
Rep(i,0,Len-1)write(C[i],' ');
putchar('\n');
}
int main()
{
freopen("water.in","r",stdin);
freopen("water.out","w",stdout);
init();
solve();
return 0;
}
```