题解 P4717 【【模板】 快速沃尔什变换】

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}$$

是不是很好背啊

代码:


#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;
}