代码

#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
#define int long long
const int mod=998244353;
inline int qpow(int a,int b){
    int ret=1;
    while(b){
        if(b&1) ret=ret*a%mod;
        a=a*a%mod;b>>=1;
    }return ret;
}
inline void up(int &x){
    if(x>=mod) x-=mod;
}
int *rev[23],*wn[23];
inline void init(){
    for(int mid=1,lg=0;mid<(1<<20);mid<<=1,lg++){
        wn[lg]=new int[mid];
        wn[lg][0]=1;
        int w=qpow(3,(mod-1)/(mid<<1));
        for(int k=1;k<mid;k++){
            wn[lg][k]=wn[lg][k-1]*w%mod;
        }
    }
}
struct poly{
    #define rep(i,l,r) for(int i=l;i<=r;i++)
    vector<int> a;
    inline poly(){}
    inline poly(int n){a.resize(n+1);}
    
    inline void ntt(int lim){
        a.resize(lim);
        int len=__lg(lim);
        if(rev[len]==nullptr){
            rev[len]=new int [lim];
            for(int i=1;i<lim;i++) rev[len][i]=rev[len][i>>1]>>1|((i&1)?(lim>>1):0);
        }
        //cerr<<"! lim : "<<lim<<endl;
        for(int i=0;i<lim;i++) if(rev[len][i]<i) swap(a[rev[len][i]],a[i]);
        for(int mid=1,lg=0;mid<lim;mid<<=1,lg++){
            for(int j=0;j<lim;j+=(mid<<1)){
                for(int k=0;k<mid;k++){
                    int x=a[j+k],y=a[j+k+mid]*wn[lg][k]%mod;
                    a[j+k]=(x+y);if(a[j+k]>=mod) a[j+k]-=mod;
                    a[j+k+mid]=(x-y);if(a[j+k+mid]<0) a[j+k+mid]+=mod;
                }
            }
        }
    }
    inline void intt(int lim){
        a.resize(lim);
        reverse(a.begin()+1,a.end());
        ntt(lim);
        int inv=qpow(lim,mod-2);
        for(int i=0;i<lim;i++) a[i]=a[i]*inv%mod;
    }
    inline int& operator [](int x){
        return a[x];
    }
    inline poly operator +(const poly&b){
        int lim=max(a.size(),b.a.size());
        poly c(lim-1);
        rep(i,0,lim-1) c[i]=(a[i]+b.a[i]),up(c[i]);
        return c;
    }
    inline poly operator -(const poly&b){
        int lim=max(a.size(),b.a.size());
        poly c(lim-1);
        rep(i,0,lim-1) c[i]=(a[i]-b.a[i]+mod),up(c[i]);
        return c;
    }
    inline poly operator *(const poly&b){
        poly c=b,d=(*this);
        int len=(int)(c.a.size())-1+(int)(d.a.size())-1;
        int lim=1;
        while(lim<=len) lim<<=1;//lim -> x^{lim-1}
        d.ntt(lim),c.ntt(lim);
        rep(i,0,lim-1) c[i]=c[i]*d[i]%mod;//,cerr<<c[i]<<" ";cerr<<endl;
        //cerr<<"OPK"<<endl;
        c.intt(lim);
        c.a.resize(len+1);
        return c;
    }
};
int n,m;
int32_t main(){
    ios::sync_with_stdio(false);
    //cerr<<n<<" "<<m<<" "<<(rev[0]==nullptr)<<endl;
    cin>>n>>m;
    //cerr<<n<<" "<<m<<" "<<(rev[0]==nullptr)<<endl;
    init();
    poly a(n),b(m);
    for(int i=0;i<=n;i++) cin>>a[i];
    for(int i=0;i<=m;i++) cin>>b[i];
    poly c=a*b;
    for(auto x:c.a) cout<<x<<" ";
}

评测结果