【洛谷4717】【模板】快速沃尔什变换（FWT模板）

点此看题面

大致题意： 有两个长度为\(2^n\)的数组\(A,B\)，且\(C_i=\sum_{j⊕k==i}A_jB_k\)分别求出当\(⊕\)为\(or,and,xor\)时的\(C\)数组。

\(FWT\)

这是一道\(FWT\)的板子题。

由于\(FWT\)太难了，所以我只会背板子（甚至连板子都不会背）。

可见代码。

代码

#include<bits/stdc++.h>

#define Tp template<typename Ty>

#define Ts template<typename Ty,typename... Ar>

#define Reg register

#define RI Reg int

#define Con const

#define CI Con int&

#define I inline

#define W while

#define N (1<<17)

#define X 998244353

#define Inc(x,y) ((x+=(y))>=X&&(x-=X))

#define Dec(x,y) ((x-=(y))<0&&(x+=X))

#define XSum(x,y) ((x)+(y)>=X?(x)+(y)-X:(x)+(y))

#define XSub(x,y) ((x)-(y)<0?(x)-(y)+X:(x)-(y))

using namespace std;

int n,a[(N<<1)+5],b[(N<<1)+5],s1[(N<<1)+5],s2[(N<<1)+5];

class FastIO

{

    private:

        #define FS 100000

        #define tc() (A==B&&(B=(A=FI)+fread(FI,1,FS,stdin),A==B)?EOF:*A++)

        #define pc(c) (C^FS?FO[C++]=c:(fwrite(FO,1,C,stdout),FO[(C=0)++]=c))

        #define tn(x) (x<<3)+(x<<1)

        #define D isdigit(c=tc())

        int T,C;char c,*A,*B,FI[FS],FO[FS],S[FS];

    public:

        I FastIO() {A=B=FI;}

        Tp I void read(Ty& x) {x=0;W(!D);W(x=tn(x)+(c&15),D);}

        Tp I void write(Ty x) {W(S[++T]=x%10+48,x/=10);W(T) pc(S[T--]);}

        Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}

        I void writec(Con char& x) {pc(x);}

        I void clear() {fwrite(FO,1,C,stdout),C=0;}

}F;

class FWT//FWT模板

{

    private:

        static const int SZ=N;int P,L;

        I void TransformOr(int* s,CI op)//or

        {

            for(RI i=1,j,k;i^P;i<<=1) for(j=0;j^P;j+=(i<<1))

                for(k=0;k^i;++k) ~op?Inc(s[i+j+k],s[j+k]):Dec(s[i+j+k],s[j+k]);

        }

        I void TransformAnd(int* s,CI op)//and

        {

            for(RI i=1,j,k;i^P;i<<=1) for(j=0;j^P;j+=(i<<1))

                for(k=0;k^i;++k) ~op?Inc(s[j+k],s[i+j+k]):Dec(s[j+k],s[i+j+k]);

        }

        I void TransformXor(int* s,CI op)//xor

        {

            for(RI i=1,j,k,tx,ty;i^P;i<<=1) for(j=0;j^P;j+=(i<<1)) for(k=0;k^i;++k)

            {

                tx=s[j+k],ty=s[i+j+k],s[j+k]=XSum(tx,ty),s[i+j+k]=XSub(tx,ty),

                !~op&&(s[j+k]=1LL*s[j+k]*(X+1>>1)%X,s[i+j+k]=1LL*s[i+j+k]*(X+1>>1)%X);

            }

        }

    public:

        I void Or(CI n,CI m,int* a,int* b)//处理or的情况

        {

            RI i,t=max(n,m);P=1,L=0;W(P<t) P<<=1,++L;

            for(TransformOr(a,1),TransformOr(b,1),i=0;i^P;++i) a[i]=1LL*a[i]*b[i]%X;

            TransformOr(a,-1);

        }

        I void And(CI n,CI m,int* a,int* b)//处理and的情况

        {

            RI i,t=max(n,m);P=1,L=0;W(P<t) P<<=1,++L;

            for(TransformAnd(a,1),TransformAnd(b,1),i=0;i^P;++i) a[i]=1LL*a[i]*b[i]%X;

            TransformAnd(a,-1);

        }

        I void Xor(CI n,CI m,int* a,int* b)//处理xor的情况

        {

            RI i,t=max(n,m);P=1,L=0;W(P<t) P<<=1,++L;

            for(TransformXor(a,1),TransformXor(b,1),i=0;i^P;++i) a[i]=1LL*a[i]*b[i]%X;

            TransformXor(a,-1);

        }

}FWT;

int main()

{

    RI i,l;for(F.read(n),n=1<<n,i=0;i^n;++i) F.read(a[i]);for(i=0;i^n;++i) F.read(b[i]);

    for(i=0;i^n;++i) s1[i]=a[i],s2[i]=b[i];for(FWT.Or(n,n,s1,s2),i=0;i^n;++i) F.write(s1[i]),F.writec(' ');F.writec('\n');

    for(i=0;i^n;++i) s1[i]=a[i],s2[i]=b[i];for(FWT.And(n,n,s1,s2),i=0;i^n;++i) F.write(s1[i]),F.writec(' ');F.writec('\n');

    for(i=0;i^n;++i) s1[i]=a[i],s2[i]=b[i];for(FWT.Xor(n,n,s1,s2),i=0;i^n;++i) F.write(s1[i]),F.writec(' ');F.writec('\n');

    return F.clear(),0;

}

【洛谷4717】【模板】快速沃尔什变换（FWT模板）的相关教程结束。