代码

/*
 * @Author: BilyHurington
 * @Date: 2020-04-18 18:20:10
 * @LastEditors: BilyHurington
 * @LastEditTime: 2020-04-20 10:11:46
 */
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,gen=3;
namespace Polynomial{
    long long W[800010];
    int rev[800010],abc[800010];
    inline int mi(int x,int y){return x>=y?x-y:x-y+mod;}
    inline int pl(int x,int y){x+=y;return x>=mod?x-mod:x;}
    inline int fast_pow(int x,int k){
        long long ans=1;
        while(k){
            if(k&1) ans=(ans*x)%mod;
            x=(x*(long long)x)%mod;
            k>>=1;
        }
        return ans;
    }
    void init(int n){
        long long tmp;
        for(int i=1;i<n;i<<=1){
            W[i]=1;tmp=fast_pow(3,(mod-1)/2/i);
            for(int j=1;j<=i-1;j++) W[i+j]=tmp*W[i+j-1]%mod;
        }
        for(int i=1;i<=n;i<<=1){
		    for(int j=1;j<i;++j) rev[i+j]=rev[i+(j>>1)]>>1|j%2*i/2;
    	}
    }
    void NTT(int *a,int len,bool tag){
        for(int i=0;i<len;i++) abc[i]=a[rev[i+len]];
        for(int i=1;i<len;i<<=1){
            for(int j=0;j<len;j+=i<<1){
                for(int k=0;k<i;k++){
                    int t=abc[i+j+k]*W[i+k]%mod;
                    abc[i+j+k]=mi(abc[j+k],t);
                    abc[j+k]=pl(abc[j+k],t);
                }
            }
        }
        if(tag){
            reverse(abc+1,abc+len);
            for(int i=0,inv=fast_pow(len,mod-2);i<len;i++) a[i]=abc[i]*(long long)inv%mod;
        }
        else for(int i=0;i<len;i++) a[i]=abc[i];
    }
}
int n,m,a[400010],b[400010];
int main(){
    Polynomial::init(262144);
    scanf("%d %d",&n,&m);
    for(int i=0;i<=n;i++) scanf("%d",&a[i]);
    for(int i=0;i<=m;i++) scanf("%d",&b[i]);
    int t;
    for(t=1;t<n+m+2;t<<=1);
    Polynomial::NTT(a,t,0);
    Polynomial::NTT(b,t,0);
    for(int i=0;i<=t;i++) a[i]=a[i]*(long long)b[i]%mod;
    Polynomial::NTT(a,t,1);
    for(int i=0;i<=n+m;i++) printf("%d ",a[i]);
    return 0;
}

评测结果