代码

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define int long long
int n,m,i,j,len;
int w[5000000],f[5000000],g[5000000];
int rev[5000000],bit,ha=998244353;
inline void getrev(int n){for(i=0;i<(1<<n);i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));}
int add(int x){return (x>=ha)?x-ha:x;}
int jian(int x){return (x<0)?x+ha:x;}
inline int qpow(int a,int b)
{
    int ans=1;
    while(b)
    {if(b%2)ans=ans*a%ha;a=a*a%ha,b/=2;};
    return ans;
}
void fft(int *a,int n,int x)
{
    if(x)reverse(a+1,a+n);
    for(int i=0;i<n;i++)if(rev[i]>i)swap(a[i],a[rev[i]]);
    for(int i=1;i<n;i<<=1)
    {
        w[0]=1; w[1]=qpow(3,(ha-1)/(i<<1));
        for(int j=2;j<i;j++)w[j]=w[j-1]*w[1]%ha;
        for(int j=0;j<n;j+=(i<<1))
            for(int k=j;k<j+i;k++)
            {
                int x=a[k],y=a[k+i]*w[k-j]%ha;
                a[k]=add(x+y),a[k+i]=jian(x-y);
            }
    }
    int ni=qpow(n,ha-2);
    if(x)for(int i=0;i<n;i++)a[i]=a[i]*ni%ha;
}
signed main()
{
    scanf("%lld%lld",&n,&m);
    for(i=0;i<=n;i++)scanf("%lld",&f[i]);
    for(i=0;i<=m;i++)scanf("%lld",&g[i]);
    len=1;
    for(;len<m+n+1;len=len<<1)bit++;getrev(bit);
    fft(f,len,0);fft(g,len,0);
    for(i=0;i<len;i++)f[i]=f[i]*g[i]%ha;
    fft(f,len,1);
    for(i=0;i<=n+m;i++)printf("%lld ",f[i]);
    return 0;
}

评测结果