代码

// luogu-judger-enable-o2
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cctype>

using namespace std;

const int MOD=998244353,G=3,Gi=332748118;

int read()
{
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}

int n,m,lim=1,l,r[4200000];

long long a[3000050],b[3000050];

long long quickpow(long long a,long long b)
{
    long long ans=1;
    while (b!=0)
    {
        if (b&1)
        {
            ans*=a;
            ans%=MOD;
        }
        a*=a;
        a%=MOD;
        b>>=1;
    }
    return ans;
}

void NTT(long long *A,int type)
{
    for (int i=0;i<lim;i++)
        if (i<r[i])
            swap(A[i],A[r[i]]);
    for (int mid=1;mid<lim;mid<<=1)
    {
        long long Wn=quickpow((type==1?G:Gi),(MOD-1)/(mid<<1));
        for (int j=0;j<lim;j+=(mid<<1))
        {
            long long W=1;
            for (int k=0;k<mid;k++)
            {
                int x=A[j+k],y=W*(A[j+k+mid])%MOD;
                A[j+k]=(x+y)%MOD;
                A[j+k+mid]=(x-y+MOD)%MOD;
                W=(W*Wn)%MOD;
            }
        }
    }
}

int main()
{
    n=read();m=read();
    for (int i=0;i<=n;i++)
        a[i]=read()%MOD;
    for (int i=0;i<=m;i++)
        b[i]=read()%MOD;
    while (lim<=n+m)
    {
        lim<<=1;
        l++;
    }
    for (int i=0;i<lim;i++)
        r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    NTT(a,1);
    NTT(b,1);
    for (int i=0;i<lim;i++)
        a[i]=(a[i]*b[i])%MOD;
    NTT(a,-1);
    int inv=quickpow(lim,MOD-2);
    for (int i=0;i<=n+m;i++)
        printf("%d ",a[i]*inv%MOD);
    return 0;
}

评测结果