代码

#include<bits/stdc++.h>
#define maxn 4000010
#define P 998244353
#define G 3
#define Gi (P+1)/G
using namespace std;
typedef long long ll;
template<typename T> inline void read(T &x)
{
    x=0;char c=getchar();bool flag=false;
    while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    if(flag)x=-x;
}
int n,m;
int rev[maxn];
ll f[maxn],g[maxn];
ll qp(ll x,ll y)
{
    ll v=1;
    while(y)
    {
        if(y&1) v=v*x%P;
        x=x*x%P,y>>=1;
    }
    return v;
}
int calc(int n)
{
    int lim=1;
    while(lim<=n) lim<<=1;
    for(int i=0;i<lim;++i)
        rev[i]=(rev[i>>1]>>1)|((i&1)?lim>>1:0);
    return lim;
}
void NTT(ll *a,int lim,int type)
{
    for(int i=0;i<lim;++i)
        if(i<rev[i])
            swap(a[i],a[rev[i]]);
    for(int len=1;len<lim;len<<=1)
    {
        ll wn=qp(type==1?G:Gi,(P-1)/(len<<1));
        for(int i=0;i<lim;i+=len<<1)
        {
            ll w=1;
            for(int j=i;j<i+len;++j,w=w*wn%P)
            {
                ll x=a[j],y=w*a[j+len]%P;
                a[j]=(x+y)%P,a[j+len]=(x-y+P)%P;
            }
        }
    }
    if(type==1) return;
    ll inv=qp(lim,P-2);
    for(int i=0;i<lim;++i) a[i]=a[i]*inv%P;
}
void mul(ll *f,ll *g)
{
    int lim=calc(n+m);
    NTT(f,lim,1),NTT(g,lim,1);
    for(int i=0;i<lim;++i) f[i]=f[i]*g[i]%P;
    NTT(f,lim,-1);
}
int main()
{
    read(n),read(m);
    for(int i=0;i<=n;++i) read(f[i]);
    for(int i=0;i<=m;++i) read(g[i]);
    mul(f,g);
    for(int i=0;i<=n+m;++i) printf("%lld ",f[i]);
    return 0;
}

评测结果