代码

#include<cstdio>
using namespace std;
#define mod 998244353
#define N 2100000
int a[N],b[N],n,m,s,rev[N],ntt[N];
int pw(int a,int p){int ans=1;while(p){if(p&1)ans=1ll*ans*a%mod;a=1ll*a*a%mod;p>>=1;}return ans;}
void dft(int s,int *a,int t)
{
    for(int i=0;i<s;i++)ntt[rev[i]]=a[i];
    for(int l=2;l<=s;l<<=1)
    {
        int st=pw(3,(mod-1)/l);
        if(t==-1)st=pw(st,mod-2);
        for(int j=0;j<s;j+=l)
            for(int k=j,s2=1;k<j+(l>>1);k++,s2=1ll*s2*st%mod)
            {
                int a1=ntt[k],a2=1ll*ntt[k+(l>>1)]*s2%mod;
                ntt[k]=(a1+a2)%mod;ntt[k+(l>>1)]=(a1-a2+mod)%mod;
            }
    }
    int inv=pw(s,t-1?mod-2:0);
    for(int i=0;i<s;i++)a[i]=1ll*ntt[i]*inv%mod;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n;i++)scanf("%d",&a[i]);
    for(int i=0;i<=m;i++)scanf("%d",&b[i]);
    int s=1;while(s<=n+m)s<<=1;for(int i=0;i<s;i++)rev[i]=rev[i/2]/2+(i&1)*s/2;dft(s,a,1);dft(s,b,1);for(int i=0;i<s;i++)a[i]=1ll*a[i]*b[i]%mod;dft(s,a,-1);for(int i=0;i<=n+m;i++)printf("%d ",a[i]);
}

评测结果