2018-team4-modules-快速数论变换2(NTT)

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{


#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
const int maxn=100005,fmaxn=19,Fmaxn=(1<<fmaxn);
const ll mod=998244353;
namespace {
    inline ll Pow(ll a,ll b) {
        ll res=1;
        while(b) {
            if(b&1)
                res=res*a%mod;
            a=a*a%mod;
            b>>=1;
        }
        return res;
    }
    inline ll Inv(const ll &x) {
        return Pow(x,mod-2);
    }
    inline ll Add(const ll &x,const ll &y) {
        ll res=x+y;
        if(res>=mod)
            res-=mod;
        return res;
    }
    inline ll Sub(const ll &x,const ll &y) {
        ll res=x-y;
        if(res<0)
            res+=mod;
        return res;
    }
    inline ll Mul(const ll &x,const ll &y) {
        ll res=x*y;
        if(res>=mod)
            res%=mod;
        return res;
    }
    inline ll Div(const ll &x,const ll &y) {
        ll res=x*Inv(y);
        if(res>=mod)
            res%=mod;
        return res;
    }
}
namespace Transform {
    const int G=3;
    int mx=0,rev[Fmaxn],A[Fmaxn],B[Fmaxn],C[Fmaxn],W[fmaxn][Fmaxn];
    inline void DFT(int *a,int n) {
        if(mx<n) {
            for(int i=mx;i<n;++i) {
                int len=(1<<i);
                ll w0=Pow(G,(mod-1)/(len<<1)),w=1;
                for(int j=0;j<len;++j)
                    W[i][j]=w,w=Mul(w,w0);
            }
            mx=n;
        }
        rev[0]=0;
        for(int i=1;i<(1<<n);++i) {
            rev[i]=i&1?rev[i^1]|(1<<(n-1)):rev[i>>1]>>1;
            if(i<rev[i])
                swap(a[i],a[rev[i]]);
        }
        for(int l=0;l<n;++l) {
            int len=(1<<l);
            for(int i=0;i<(1<<n);i+=(len<<1)) {
                for(int j=0;j<len;++j) {
                    int x=a[i+j],y=Mul(a[i+j+len],W[l][j]);
                    a[i+j]=Add(x,y),a[i+j+len]=Sub(x,y);
                }
            }
        }
    }
    inline void IDFT(int *a,int n) {
        reverse(a+1,a+(1<<n));
        DFT(a,n);
        ll invn=Inv((1<<n));
        for(int i=0;i<(1<<n);++i)
            a[i]=Mul(a[i],invn);
    }
    inline vector<int> FFT(vector<int> a,vector<int> b) {
        int la=a.size()-1,lb=b.size()-1,lc=la+lb+1,lim=0;
        while((1<<lim)<lc)
            lim++;
        vector<int>c;
        c.resize(lc);
        for(int i=0;i<(1<<lim);++i)
            A[i]=B[i]=0;
        for(int i=0;i<=la;++i)
            A[i]=a[i];
        for(int i=0;i<=lb;++i)
            B[i]=b[i];
        DFT(A,lim),DFT(B,lim);
        for(int i=0;i<(1<<lim);++i)
            A[i]=Mul(A[i],B[i]);
        IDFT(A,lim);
        for(int i=0;i<lc;++i)
            if(A[i])
                c[i]=A[i];
        return c;
    }
}


}}}

#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
const int maxn=100005,fmaxn=19,Fmaxn=(1<<fmaxn);
const ll mod=998244353;
namespace {
    inline ll Pow(ll a,ll b) {
        ll res=1;
        while(b) {
            if(b&1)
                res=res*a%mod;
            a=a*a%mod;
            b>>=1;
        }
        return res;
    }
    inline ll Inv(const ll &x) {
        return Pow(x,mod-2);
    }
    inline ll Add(const ll &x,const ll &y) {
        ll res=x+y;
        if(res>=mod)
            res-=mod;
        return res;
    }
    inline ll Sub(const ll &x,const ll &y) {
        ll res=x-y;
        if(res<0)
            res+=mod;
        return res;
    }
    inline ll Mul(const ll &x,const ll &y) {
        ll res=x*y;
        if(res>=mod)
            res%=mod;
        return res;
    }
    inline ll Div(const ll &x,const ll &y) {
        ll res=x*Inv(y);
        if(res>=mod)
            res%=mod;
        return res;
    }
}
namespace Transform {
    const int G=3;
    int mx=0,rev[Fmaxn],A[Fmaxn],B[Fmaxn],C[Fmaxn],W[fmaxn][Fmaxn];
    inline void DFT(int *a,int n) {
        if(mx<n) {
            for(int i=mx;i<n;++i) {
                int len=(1<<i);
                ll w0=Pow(G,(mod-1)/(len<<1)),w=1;
                for(int j=0;j<len;++j)
                    W[i][j]=w,w=Mul(w,w0);
            }
            mx=n;
        }
        rev[0]=0;
        for(int i=1;i<(1<<n);++i) {
            rev[i]=i&1?rev[i^1]|(1<<(n-1)):rev[i>>1]>>1;
            if(i<rev[i])
                swap(a[i],a[rev[i]]);
        }
        for(int l=0;l<n;++l) {
            int len=(1<<l);
            for(int i=0;i<(1<<n);i+=(len<<1)) {
                for(int j=0;j<len;++j) {
                    int x=a[i+j],y=Mul(a[i+j+len],W[l][j]);
                    a[i+j]=Add(x,y),a[i+j+len]=Sub(x,y);
                }
            }
        }
    }
    inline void IDFT(int *a,int n) {
        reverse(a+1,a+(1<<n));
        DFT(a,n);
        ll invn=Inv((1<<n));
        for(int i=0;i<(1<<n);++i)
            a[i]=Mul(a[i],invn);
    }
    inline vector<int> FFT(vector<int> a,vector<int> b) {
        int la=a.size()-1,lb=b.size()-1,lc=la+lb+1,lim=0;
        while((1<<lim)<lc)
            lim++;
        vector<int>c;
        c.resize(lc);
        for(int i=0;i<(1<<lim);++i)
            A[i]=B[i]=0;
        for(int i=0;i<=la;++i)
            A[i]=a[i];
        for(int i=0;i<=lb;++i)
            B[i]=b[i];
        DFT(A,lim),DFT(B,lim);
        for(int i=0;i<(1<<lim);++i)
            A[i]=Mul(A[i],B[i]);
        IDFT(A,lim);
        for(int i=0;i<lc;++i)
            if(A[i])
                c[i]=A[i];
        return c;
    }
}