代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=6e5+3,mod=998244353;
int m1,m2,lgn,n;
int f[N],g[N],r[N],inv;
int qpow(int x,int y){
    int res=1;
    while(y){
        if(y&1)res=res*x%mod;
        x=x*x%mod,y>>=1;
    }
    return res;
}
void change(int x[]){
    for(int i=0;i<n;i++){
        r[i]=r[i>>1]>>1;
        if(i&1)r[i]|=(n>>1);
    }
    for(int i=0;i<n;i++)if(i<r[i])swap(x[i],x[r[i]]);
}
void ntt(int x[],int opt){
    change(x);
    for(int h=2;h<=n;h<<=1){
        int wn=qpow(3,(mod-1)/h);
        if(opt==-1)wn=qpow(wn,mod-2);
        for(int i=0;i<n;i+=h){
            int w=1;
            for(int k=i;k<i+h/2;k++){
                int u=x[k],tmp=w*x[k+h/2]%mod;
                x[k]=(u+tmp)%mod,x[k+h/2]=(u-tmp+mod)%mod;
                w=(w*wn)%mod;
            }
        }
    }
    if(opt==-1)
        for(int i=0;i<n;i++)x[i]=x[i]*inv%mod;
}
main(){
    scanf("%lld%lld",&m1,&m2);
    for(int i=0;i<m1;i++)scanf("%lld",&f[i]);
    for(int i=0;i<m2;i++)scanf("%lld",&g[i]);
    lgn=__lg(m1+m2-2)+1;
    n=1<<lgn;
    inv=qpow(n,mod-2);
    ntt(f,1),ntt(g,1);
    for(int i=0;i<n;i++)f[i]*=g[i],f[i]%=mod;
    ntt(f,-1);
    for(int i=0;i<m1+m2-1;i++)printf("%lld ",f[i]);
}

评测结果