FFT与NTT模板

FTT

加了三次变两次，预处理单位根
跑的比NTT快多了（不愧是三次变两次啊）

#include<bits/stdc++.h>//FFT
using namespace std;
#define db double
#define maxn 10000005
const double Pi=acos(-1.0);
template<typename T>
inline void read(T& x)
{
    x=0;char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) x=x*10+c-'0',c=getchar();
}
struct com
{
    db re,im;
    com(){}
    com(db a,db b):re(a),im(b){}
    inline com friend operator + (com a,com b)
        {
            return com(a.re+b.re,a.im+b.im);
        }
    inline com friend operator - (com a,com b)
        {
            return com(a.re-b.re,a.im-b.im);
        }
    inline com friend operator * (com a,com b)
        {
            return com(a.re*b.re-a.im*b.im,a.re*b.im+a.im*b.re);
        }
}a[maxn];
int l,r[maxn],n,m,lim=1;
long double Cos[30],Sin[30];
void fft(com* A,int type)
{
    for(int i=0;i<lim;++i)
        if(i<r[i]) swap(A[i],A[r[i]]);
    for(int mid=1,tp=0;mid<lim;mid<<=1,++tp)
    {
        com Wn(Cos[tp],type*Sin[tp]);
        for(int R=mid<<1,j=0;j<lim;j+=R)
        {
            com W(1,0);
            for(int k=0;k<mid;++k,W=W*Wn)
            {
                com x=A[j+k],y=W*A[mid+j+k];
                A[j+k]=x+y;
                A[j+k+mid]=x-y;
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    register int i;int tp;
    for(i=0;i<=n;++i) read(tp),a[i].re=tp;
    for(i=0;i<=m;++i) read(tp),a[i].im=tp;
    while(lim<=n+m) lim<<=1,++l;
    for(int i=1,tp=0;i<lim;i<<=1,++tp)
        Cos[tp]=cos(Pi/i),Sin[tp]=sin(Pi/i);
    for(i=0;i<lim;++i)
        r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    fft(a,1);
    for(i=0;i<lim;++i) a[i]=a[i]*a[i];
    fft(a,-1);a
    for(i=0;i<=n+m;++i)
        printf("%d ",(int)(a[i].im/(2.0*lim)+0.5));
    return 0;
}

NTT

据\(\color{red}{a}\)\(nson\)讲\(NTT\)主要是慢在取模上
这里模数是\(998244353\)

#include<bits/stdc++.h>//NTT
using namespace std;
#define db double
#define maxn 10000005
#define ll long long
#define p 998244353
#define g 3
#define ginv 332748118
template<typename T>
inline void read(T& x)
{
    x=0;char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) x=x*10+c-'0',c=getchar();
}
ll a[maxn],b[maxn];
int l,r[maxn],n,m,lim=1;
inline ll qpow(ll x,ll y)
{
    ll ans=1;
    while(y)
    {
        if(y&1) ans=(ans*x)%p;
        x=(x*x)%p;
        y>>=1;
    }
    return ans;
}
void fft(ll* A,int type)
{
    for(int i=0;i<lim;++i)
        if(i<r[i]) swap(A[i],A[r[i]]);
    for(int mid=1;mid<lim;mid<<=1)
    {
        ll Wn=qpow((type==1)?g:ginv,(p-1)/(mid<<1));
        for(int R=mid<<1,j=0;j<lim;j+=R)
        {
            ll W=1;
            for(int k=0;k<mid;++k,W=W*Wn%p)
            {
                ll x=A[j+k],y=W*A[mid+j+k]%p;
                A[j+k]=(x+y);if(A[j+k]>p) A[j+k]-=p;
                A[j+k+mid]=x-y;if(A[j+k+mid]<0) A[j+k+mid]+=p;
            }
        }
    }
}
int main()
{
    read(n),read(m);
    register int i;
    for(i=0;i<=n;++i) read(a[i]);
    for(i=0;i<=m;++i) read(b[i]);
    while(lim<=n+m) lim<<=1,++l;
    for(i=0;i<lim;++i)
        r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    fft(a,1);fft(b,1);
    for(i=0;i<=lim;++i) a[i]=a[i]*b[i]%p;
    fft(a,-1);
    ll inv=qpow(lim,p-2);
    for(i=0;i<=n+m;++i)
        printf("%d ",(a[i]*inv%p));
    return 0;
}

FFT与NTT模板

原文：https://www.cnblogs.com/123789456ye/p/12202987.html