代码

#include<bits/stdc++.h>
#define Inc(x,y) ((x+=y)>=mod&&(x-=mod))
#define Dec(x,y) ((x-=y)<0&&(x+=mod))
using namespace std;
const int mod=998244353;
const int gen=3,ivg=332748118;
const int N=1<<21|5;
namespace Math{
	inline int fmo(const int x,const int y){
		long long t=1ll*x*y;
		long long h=(t>>29)*2309898375ll>>32;
		t-=h*mod;return t>=mod?t-mod:t;
	}inline int fp(int x,int y){
		int ans=1;for(;y;y>>=1,x=fmo(x,x))(y&1)&&(ans=fmo(ans,x));
		return ans;
	}
}namespace Poly{
	using Math::fp;
	using Math::fmo;
	struct lsp{
		int A[40],B[40];
		lsp(const int x=gen){
			A[22]=fp(x,mod>>22);B[(1<<22)%37]=22;
			for(int i=22;i;i--)A[(i-1)]=fmo(A[i],A[i]),B[(1<<(i-1))%37]=i-1;
		}inline int operator ()( int x){return A[B[x%37]];}
	}PW_GEN;
	int pw[N],inited=0,rev[N];
	inline void initw( int x){
		inited=x;for(int i=0;i<x;i++)rev[i]=rev[i>>1]>>1|((i&1)?x>>1:0);
		for(int i=1;i<x;i<<=1){
			pw[i]=1;pw[i+1]=PW_GEN(i<<1);
			for(int j=2;j<i;j++)pw[i+j]=fmo(pw[i+j-1],pw[i+1]);
		}
	}
	inline void ntt(int *a, int lim, int fl=1){
		(inited!=lim)&&(initw(lim),0);
		for(int i=0;i<lim;i++)(i<rev[i])&&(swap(a[i],a[rev[i]]),0);
		for(int k=1;k<lim;k<<=1)
			for(int i=0;i<k;++i)
				for(int j=0;j<lim;j+=k<<1){
					int t=fmo(pw[i+k],a[i+j+k]);a[i+j+k]=a[i+j];
					Dec(a[i+j+k],t);Inc(a[i+j],t);
				}
		if(!fl){
			for(int iv=fp(lim,mod-2),i=0;i<lim;i++)a[i]=fmo(a[i],iv);
			reverse(a+1,a+lim);
		}
	}
	int A[N],B[N];
	#define bs basic_string<int>
	struct poly{
		bs f;int n;
		poly( int *a=NULL, int x=0){
			f.resize(n=x);for(int i=0;i<n;i++)f[i]=a[i];
		}inline int size(){return n;}
		inline int& operator []( int x){return f[x];}
		inline  int operator []( int x)const{return f[x];}
		inline poly operator +(const poly& a){
			for(int i=0;i<n;i++)A[i]=f[i];for(int i=0;i<a.n;i++)B[i]=a[i];
			int m=max(n,a.n);for(int i=0;i<m;i++)Inc(A[i],B[i]);
			poly b=poly(A,m);for(int i=0;i<m;i++)A[i]=B[i]=0;
			return b;
		}inline poly operator -(const poly& a){
			for(int i=0;i<n;i++)A[i]=f[i];for(int i=0;i<a.n;i++)B[i]=a[i];
			int m=max(n,a.n);for(int i=0;i<m;i++)Dec(A[i],B[i]);
			poly b=poly(A,m);for(int i=0;i<m;i++)A[i]=B[i]=0;return b;
		}inline poly operator *(const poly& a){
			for(int i=0;i<n;i++)A[i]=f[i];for(int i=0;i<a.n;i++)B[i]=a[i];
			int lim=1;while(lim<n+a.n)lim<<=1;ntt(A,lim);ntt(B,lim);
			for(int i=0;i<lim;i++)A[i]=fmo(A[i],B[i]);ntt(A,lim,0);
			poly b=poly(A,n+a.n-1);for(int i=0;i<lim;i++)A[i]=B[i]=0;
			return b;
		}
	};
	#undef bs
}
using Poly::poly;
int f[N],g[N],n,m;
poly h;
int main(){
	scanf("%d%d",&n,&m);++n;++m;
	for(int i=0;i<n;i++)scanf("%d",f+i);
	for(int i=0;i<m;i++)scanf("%d",g+i);
	h=poly(f,n)*poly(g,m);
	for(int i=0;i<h.n;i++)printf("%d ",h[i]);
	return 0;
}

评测结果