代码

#include<cctype>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
const int N=1<<18|1,P=998244353;
int n,m,lim,rev[N],w[N],f[N],g[N];
int read(){int x=0,c=getchar();while(isspace(c))c=getchar();while(isdigit(c))(x*=10)+=c&15,c=getchar();return x;}
void inc(int&a,int b){a+=b-P,a+=a>>31&P;}
int sub(int a,int b){return a-=b,a+=a>>31&P;}
int mul(int a,int b){return 1ll*a*b%P;}
int pow(int a,int k){int r=1;for(;k;k>>=1,a=mul(a,a))if(k&1)r=mul(a,r);return r;}
void init(int n)
{
    int p=(lim=1<<(32-__builtin_clz(n)))>>1,g=pow(3,(P-1)/lim);w[p]=1;
    for(int i=1;i<lim;++i) rev[i]=(rev[i>>1]>>1)|(i&1? p:0);
    for(int i=p+1;i<lim;++i) w[i]=mul(w[i-1],g);
    for(int i=p-1;i;--i) w[i]=w[i<<1];
}
void NTT(int*a,int f)
{
    if(!~f) std::reverse(a+1,a+lim);
    for(int i=1;i<lim;++i) if(i<rev[i]) std::swap(a[i],a[rev[i]]);
    for(int i=1;i<lim;i<<=1) for(int j=0,d=i<<1;j<lim;j+=d) for(int k=0,x;k<i;++k) x=mul(a[i+j+k],w[i+k]),a[i+j+k]=sub(a[j+k],x),inc(a[j+k],x);
    if(!~f) for(int i=0,x=P-(P-1)/lim;i<lim;++i) a[i]=mul(a[i],x);
}
int main()
{
    n=read(),m=read(),init(n+m);
    for(int i=0;i<=n;++i) f[i]=read();
    for(int i=0;i<=m;++i) g[i]=read();
    NTT(f,1),NTT(g,1);
    for(int i=0;i<lim;++i) f[i]=mul(f[i],g[i]);
    NTT(f,-1);
    for(int i=0;i<=n+m;++i) printf("%d ",f[i]);
}

评测结果