传送门
FFT
#include<bits/stdc++.h>
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return x*f;
}
#define MN 2097152
const double Pi=std::acos(-1.);
struct complex
{
double x,y;
complex(double x=0,double y=0):x(x),y(y){}
inline complex operator+(const complex& o)const{return complex(x+o.x,y+o.y);}
inline complex operator-(const complex& o)const{return complex(x-o.x,y-o.y);}
inline complex operator*(const complex& o)const{return complex(x*o.x-y*o.y,x*o.y+y*o.x);}
inline void swap(complex& o){register complex t=o;o=(*this);*this=t;}
}a[MN],b[MN];
int N,di,pos[MN];
inline void FFT(complex *a,int type)
{
register int i,j,p,k;
for(i=0;i<N;++i)if(i<pos[i])a[i].swap(a[pos[i]]);
for(i=1;i<N;i<<=1)
{
complex wn(cos(Pi/i),type*sin(Pi/i));
for(p=i<<1,j=0;j<N;j+=p)
{
complex w(1,0);
for(k=0;k<i;++k,w=w*wn)
{
complex X=a[j+k],Y=w*a[j+i+k];
a[j+k]=X+Y;a[j+i+k]=X-Y;
}
}
}
}
int main()
{
register int n,m,i;
n=read();m=read();
for(i=0;i<=n;++i) a[i].x=read();
for(i=0;i<=m;++i) b[i].x=read();
for(N=1;N<=n+m;N<<=1,di++);
for(i=0;i<N;++i) pos[i]=(pos[i>>1]>>1)|((i&1)<<(di-1));
FFT(a,1);FFT(b,1);
for(i=0;i<N;++i) a[i]=a[i]*b[i];
FFT(a,-1);
for(i=0;i<=n+m;++i) printf("%d ",(int)(a[i].x/N+.5));
return 0;
}
NTT
#include<bits/stdc++.h>
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define swap(x,y) (x^=y^=x^=y)
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return x*f;
}
#define MN 2097152
int N,di,pos[MN];
ll a[MN],b[MN],invN;
#define mod 998244353
#define g 3
#define invg 332748118
inline ll fpow(ll x,int m){ll res=1;for(;m;m>>=1,x=x*x%mod) (m&1)?res=res*x%mod:0;return res;}
inline void NTT(ll *a,int type)
{
register int i,j,p,k;
for(i=0;i<N;++i)if(i<pos[i]) swap(a[i],a[pos[i]]);
for(i=1;i<N;i<<=1)
{
ll wn=fpow(type>0?g:invg,(mod-1)/(i<<1));
for(p=i<<1,j=0;j<N;j+=p)
{
ll w=1;
for(k=0;k<i;++k,w=w*wn%mod)
{
ll X=a[j+k],Y=w*a[j+i+k]%mod;
a[j+k]=(X+Y)%mod;a[j+i+k]=(X-Y+mod)%mod;
}
}
}
}
int main()
{
register int n,m,i;
n=read();m=read();
for(i=0;i<=n;++i) a[i]=(read()+mod)%mod;
for(i=0;i<=m;++i) b[i]=(read()+mod)%mod;
for(N=1;N<=n+m;N<<=1,di++);
for(i=0;i<N;++i) pos[i]=(pos[i>>1]>>1)|((i&1)<<(di-1));
NTT(a,1);NTT(b,1);
for(i=0;i<N;++i) a[i]=a[i]*b[i]%mod;
NTT(a,-1);invN=fpow(N,mod-2);
for(i=0;i<=n+m;++i) printf("%lld ",a[i]*invN%mod);
return 0;
}
Blog来自PaperCloud，未经允许，请勿转载，TKS！