FFT,NTT,FWT

• 并没有讲解.只是记录用.
• 今天心血来潮打了下板子,发现我以前打的 \(FFT,NNT\) 都是假的???而且小数据都能 \(A\) ,大数据都 \(WA\) ???
• 还好今天写了一下,不然可能要打一辈子的假算法...

\(FFT\)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=4e6+10;
inline int read()
{
    int x=0;
    bool pos=1;
    char ch=getchar();
    for(; !isdigit(ch); ch=getchar())
        if(ch=='-')
            pos=0;
    for(; isdigit(ch); ch=getchar())
        x=x*10+ch-'0';
    return pos?x:-x;
}
struct cp
{
    double x,y;
    cp(double xx=0,double yy=0)
    {
        x=xx;
        y=yy;
    }
    cp operator +(const cp &b) const
    {
        return cp(x+b.x,y+b.y);
    }
    cp operator -(const cp &b) const
    {
        return cp(x-b.x,y-b.y);
    }
    cp operator *(const cp &b) const
    {
        return cp(x*b.x-y*b.y,x*b.y+y*b.x);
    }
};
const double PI=acos(-1.0);
int rev[MAXN];
void init(int n,int lim)
{
    for(int i=0; i<n; ++i)
    {
        for(int j=0; j<lim; ++j)
            if((i>>j)&1)
                rev[i]|=1<<(lim-j-1);
    }
}
void FFT(cp *a,int n,bool invflag)
{
    for(int i=0; i<n; ++i)
    {
        if(i<rev[i])
            swap(a[i],a[rev[i]]);
    }
    for(int l=2; l<=n; l<<=1)
    {
        int m=l>>1;
        cp wi=cp(cos(2*PI/l),sin(2*PI/l));
        if(invflag)
            wi=cp(cos(2*PI/l),-sin(2*PI/l));
        for(cp *p=a; p!=a+n; p+=l)
        {
            cp w=cp(1,0);
            for(int i=0; i<m; ++i)
            {
                cp t=w*p[i+m];
                p[i+m]=p[i]-t;
                p[i]=p[i]+t;
                w=w*wi;
            }
        }
    }
    if(invflag)
    {
        for(int i=0; i<n; ++i)
            a[i].x/=n,a[i].y/=n;
    }
}
int n,m;
cp a[MAXN],b[MAXN];
int main()
{
    n=read(),m=read();
    ++n,++m;
    for(int i=0; i<n; ++i)
        a[i]=cp((double)read(),0);
    for(int i=0; i<m; ++i)
        b[i]=cp((double)read(),0);
    int N=1,lim=0;
    while(N<n+m-1)
        N<<=1,++lim;
    init(N,lim);
    FFT(a,N,false);
    FFT(b,N,false);
    for(int i=0; i<N; ++i)
        a[i]=a[i]*b[i];
    FFT(a,N,true);
    for(int i=0; i<n+m-1; ++i)
        printf("%d ",(int)(a[i].x+0.5));
    return 0;
}

\(NTT\)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=4e6+10;
inline int read()
{
    int x=0;
    bool pos=1;
    char ch=getchar();
    for(; !isdigit(ch); ch=getchar())
        if(ch=='-')
            pos=0;
    for(; isdigit(ch); ch=getchar())
        x=x*10+ch-'0';
    return pos?x:-x;
}
const int P=998244353,G=3;
int add(int a,int b)
{
    return (a + b) % P;
}
int mul(int a,int b)
{
    return 1LL * a * b % P;
}
int fpow(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1)
            res=mul(res,a);
        a=mul(a,a);
        b>>=1;
    }
    return res;
}
int inv(int x)
{
    return fpow(x,P-2);
}
int rev[MAXN];
void init(int n,int lim)
{
    for(int i=0; i<n; ++i)
    {
        for(int j=0; j<lim; ++j)
            if((i>>j)&1)
                rev[i]|=1<<(lim-j-1);
    }
}
void NTT(int *a,int n,bool invflag)
{
    for(int i=0; i<n; ++i)
    {
        if(i<rev[i])
            swap(a[i],a[rev[i]]);
    }
    for(int l=2; l<=n; l<<=1)
    {
        int gi=fpow(G,(P-1)/l);
        if(invflag)
            gi=inv(gi);
        int m=l>>1;
        for(int *p=a;p!=a+n;p+=l)
        {
            int g=1;
            for(int i=0; i<m; ++i)
            {
                int t=mul(g,p[i+m]);
                p[i+m]=add(p[i],P-t);
                p[i]=add(p[i],t);
                g=mul(g,gi);
            }
        }
    }
    if(invflag)
    {
        int Invn=inv(n);
        for(int i=0; i<n; ++i)
            a[i]=mul(a[i],Invn);
    }
}
int n,m;
int a[MAXN],b[MAXN];
int main()
{
    n=read(),m=read();
    ++n,++m;
    for(int i=0; i<n; ++i)
        a[i]=read();
    for(int i=0; i<m; ++i)
        b[i]=read();
    int N=1,lim=0;
    while(N<n+m-1)
        N<<=1,++lim;
    init(N,lim);
    NTT(a,N,false);
    NTT(b,N,false);
    for(int i=0; i<N; ++i)
        a[i]=mul(a[i],b[i]);
    NTT(a,N,true);
    for(int i=0; i<n+m-1; ++i)
        printf("%d ",a[i]);
    return 0;
}

\(FWT\)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pii pair<int,int>
inline int read()
{
    int x=0;
    bool pos=1;
    char ch=getchar();
    for(; !isdigit(ch); ch=getchar())
        if(ch=='-')
            pos=0;
    for(; isdigit(ch); ch=getchar())
        x=x*10+ch-'0';
    return pos?x:-x;
}
void FWT(int *a,int n,int op)
{
    for(int l=2; l<=n; l<<=1)
    {
        int m=l>>1;
        for(int *p=a; p!=a+n; p+=l)
        {
            for(int i=0; i<m; ++i)
            {
                int x0=p[i],x1=p[i+m];
                if(op==1)//or
                {
                    p[i]=x0;
                    p[i+m]=x0+x1;
                }
                if(op==2)//and
                {
                    p[i]=x0+x1;
                    p[i+m]=x1;
                }
                if(op==3)//xor
                {
                    p[i]=x0+x1;
                    p[i+m]=x0-x1;
                }
            }
        }
    }
}
void IFWT(int *a,int n,int op)
{
    for(int l=2; l<=n; l<<=1)
    {
        int m=l>>1;
        for(int *p=a; p!=a+n; p+=l)
        {
            for(int i=0; i<m; ++i)
            {
                int x0=p[i],x1=p[i+m];
                if(op==1)//or
                {
                    p[i]=x0;
                    p[i+m]=x1-x0;
                }
                if(op==2)//and
                {
                    p[i]=x0-x1;
                    p[i+m]=x1;
                }
                if(op==3)//xor
                {
                    p[i]=(x0+x1)>>1;
                    p[i+m]=(x0-x1)>>1;
                }
            }
        }
    }
}
int main()
{

    return 0;
}

FFT,NTT,FWT

原文：https://www.cnblogs.com/jklover/p/10666102.html