代码

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
inline int fp(int x,int y){
	int ans=1;for(;y;y>>=1,x=1ll*x*x%mod)
		if(y&1)ans=1ll*ans*x%mod;
	return ans;
}
namespace Poly{
	const int N=1<<21|5;
	const int gen=3,ivg=332748118;
	int A[N],B[N],rev[N];
	struct lsp{
		int pw1[1<<15|5],pw2[1<<15|5],block;
		lsp(int x=0){
			pw1[0]=pw2[0]=1;block=1<<15;
			for(int i=1;i<=block;i++)
				pw1[i]=1ll*pw1[i-1]*x%mod;
			for(int i=1;i*block<=mod;i++)
				pw2[i]=1ll*pw2[i-1]*pw1[block]%mod;
		}inline int operator [](int x){
			if(x<0)x+=mod-1;
			return 1ll*pw1[x&32767]*pw2[x>>15]%mod;
		}
	}pw[2]={ivg,gen};
	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){
			for(int j=0;j<lim;j+=(k<<1))
				for(int i=j;i<j+k;i++){
					int t=1ll*pw[fl][mod/(k<<1)*(i-j)]*a[i+k]%mod;
					a[i+k]=(a[i]+mod-t)%mod;
					a[i]=(a[i]+t)%mod;
				}
		}if(!fl)for(int i=0,ivlim=fp(lim,mod-2);i<lim;i++)a[i]=1ll*a[i]*ivlim%mod;
	}
	inline void clra(int *a,int x){fill(a,a+x,0);}
	struct poly{
		vector<int>f;
		int n;
		poly(int x=0){
			f.clear();n=0;
			if(x)f.push_back(x),++n;
		}
		poly(int *a,int x){
			n=x;f.clear();
			for(int i=0;i<n;i++)
				f.push_back(a[i]);
		}
		poly(vector<int>& a,int x){
			n=x;f.clear();
			for(int i=0;i<n;i++)
				f.push_back(a[i]);
		}
		int& operator [](int x){return f[x];}
		const int operator [](int x)const{return f[x];}
		inline int size(){return n;}
		inline void resize(int x){f.resize(n=x);}
		inline poly getp(int x){
			for(int i=0;i<n&&i<x;i++)A[i]=f[i];poly a=poly(A,x);clra(A,x);return a;
		}
		inline void getarry(int *a){
			for(int i=0;i<n;i++)a[i]=f[i];
		}
		inline poly operator *(poly a){
			getarry(A);a.getarry(B);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]=1ll*A[i]*B[i]%mod;
			ntt(A,lim,0);poly b=poly(A,n+a.n-1);
			clra(A,lim);clra(B,lim);return b;
		}inline poly operator +(poly a){
			getarry(A);a.getarry(B);int lim=max(n,a.n);
			for(int i=0;i<lim;i++)A[i]=(A[i]+B[i])%mod;
			poly b=poly(A,lim);return b;
		}inline poly operator -(poly a){
			getarry(A);a.getarry(B);int lim=max(n,a.n);
			for(int i=0;i<lim;i++)A[i]=(A[i]+mod-B[i])%mod;
			poly b=poly(A,lim);return b;
		}
		inline poly inv(){
			poly a(fp(f[0],mod-2));
			for(int i=1;i<n;i<<=1){
				poly b=a*a;
				b=b*getp(i<<1);
				a=a+a-b.getp(i<<1);
			}
			return a.getp(n);
		}
	};
}
using Poly::poly;
const int N=1e6+5;
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;
}

评测结果