代码

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5,mod=998244353;
int n,m,a[N],b[N],res[N],len,r[N],inv;
int mul(int x,int n,int mod){
	int ans=mod!=1;
	for(;n;n>>=1,x=1ll*x*x%mod)
		if(n&1) ans=1ll*ans*x%mod;
	return ans;
}
void NTT(int a[N],int n,int op){	//op=1/-1: DFT/IDFT
	for(int i=0;i<n;i++)
		if(i<r[i]) swap(a[i],a[r[i]]);
	for(int k=2;k<=n;k<<=1){
		int m=k>>1,x=mul(3,(mod-1)/k,mod),w=1,v; 
		if(op==-1) x=mul(x,mod-2,mod);
		for(int i=0;i<n;i+=k,w=1)
			for(int j=i;j<i+m;j++) v=1ll*w*a[j+m]%mod,a[j+m]=(a[j]-v+mod)%mod,a[j]=(a[j]+v)%mod,w=1ll*w*x%mod;
	}
	if(op==-1){
		inv=mul(len,mod-2,mod);
		for(int i=0;i<n;i++) a[i]=1ll*a[i]*inv%mod;
	}
} 
signed main(){
	scanf("%d%d",&n,&m),n++,m++;
	for(int i=0;i<n;i++)
		scanf("%d",&a[i]);
	for(int i=0;i<m;i++)
		scanf("%d",&b[i]);
	for(len=1;len<=n+m;len<<=1); 
	for(int i=0;i<len;i++)
		r[i]=(r[i>>1]>>1)|((i&1)?len>>1:0);
	NTT(a,len,1),NTT(b,len,1);
	for(int i=0;i<len;i++) a[i]=1ll*a[i]*b[i]%mod;
	NTT(a,len,-1);
	for(int i=0;i<n+m-1;i++) printf("%d ",a[i]);
	return 0;
}

评测结果