代码

#include<bits/stdc++.h>
using namespace std;
const int N=4e6+5;
const int p=998244353;
const int gen=3;
inline bool isnum(char &ch){return ch>='0'&&ch<='9';}
inline int rd(){
	int x=0,fl=1;char ch;
	while(!isnum(ch=getchar()))fl=ch=='-'?-1:1;
	for(x=ch^48;isnum(ch=getchar());x=(x<<1)+(x<<3)+(ch^48));
	return x*fl;
}
inline int fp(int x,int y){
	int ans=1;
	for(;y;y>>=1){
		if(y&1)ans=(1ll*ans*x)%p;
		x=(1ll*x*x)%p;
	}
	return ans;
}
namespace NTT{
	int rev[N],A[N],B[N];
	inline void ntt(int *a,int lim,int fl=1){
		for(int i=0;i<lim;i++){
			rev[i]=(rev[i>>1]>>1)|((i&1)*(lim>>1));
			if(i<rev[i])swap(a[i],a[rev[i]]);
		}
		for(int k=1;k<lim;k<<=1){
			int o=fp(gen,(p-1)/(k<<1));if(!fl)o=fp(o,p-2);
			for(int j=0;j<lim;j+=k<<1)
				for(int i=j,w=1;i<j+k;i++,w=(1ll*w*o)%p){
					int t=(1ll*w*a[i+k])%p;
					a[i+k]=(a[i]+p-t)%p;
					a[i]=(a[i]+t)%p;
				}
		}
		if(!fl)for(int i=0,iv=fp(lim,p-2);i<lim;i++)a[i]=(1ll*a[i]*iv)%p;
	}
	inline void mul(int *a,int *b,int n,int m,int *c){
		int lim=1;while(lim<n+m)lim<<=1;
		for(int i=0;i<n;i++)A[i]=a[i];for(int i=0;i<m;i++)B[i]=b[i];
		ntt(A,lim);ntt(B,lim);for(int i=0;i<lim;i++)c[i]=(1ll*A[i]*B[i])%p;
		ntt(c,lim,0);for(int i=0;i<lim;i++)A[i]=B[i]=0;
	}
}
int n,m,f[N],g[N],h[N];
int main(){
	n=rd();m=rd();
	for(int i=0;i<=n;i++)f[i]=rd();
	for(int i=0;i<=m;i++)g[i]=rd();
	NTT::mul(f,g,n+1,m+1,h);
	for(int i=0;i<=n+m;i++)printf("%d ",h[i]);
	return 0;
}

评测结果