代码

#include<bits/stdc++.h>
using namespace std;
const int p=998244353;
const int gen=3;
const int N=2e6+5;
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];
	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;
	}
}
namespace Poly{
	int A[N],B[N];
	using NTT::ntt;
	struct poly{
		vector<int>f;int n;
		poly(){f.clear();n=0;}
		poly(int *a,int len){
			n=len;f.clear();
			for(int i=0;i<n;i++)
				f.push_back(a[i]);
		}
		int& operator [](const int& x){
			while(n<=x)f.push_back(0),n++;
			return f[x];
		}
	};
	poly operator +(const poly& a,const poly& b){
		for(int i=0;i<a.n;i++)A[i]=a.f[i];
		for(int i=0;i<b.n;i++)B[i]=b.f[i];
		int n=max(a.n,b.n);
		for(int i=0;i<n;i++)A[i]=(A[i]+B[i])%p;poly c=poly(A,n);
		for(int i=0;i<n;i++)A[i]=B[i]=0;return c;
	}
	poly operator -(const poly& a,const poly& b){
		for(int i=0;i<a.n;i++)A[i]=a.f[i];
		for(int i=0;i<b.n;i++)B[i]=b.f[i];
		int n=max(a.n,b.n);
		for(int i=0;i<n;i++)A[i]=(A[i]+p-B[i])%p;poly c=poly(A,n);
		for(int i=0;i<n;i++)A[i]=B[i]=0;return c;
	}
	poly operator *(const poly& a,const poly& b){
		for(int i=0;i<a.n;i++)A[i]=a.f[i];
		for(int i=0;i<b.n;i++)B[i]=b.f[i];
		int lim=1;while(lim<a.n+b.n)lim<<=1;
		ntt(A,lim);ntt(B,lim);for(int i=0;i<lim;i++)A[i]=(1ll*A[i]*B[i])%p;
		ntt(A,lim,0);poly c=poly(A,a.n+b.n-1);
		for(int i=0;i<lim;i++)A[i]=B[i]=0;
		return c;
	}
}
using Poly::poly;
poly a,b,c;
int n,m,f[N],g[N];
int main(){
	n=rd();m=rd();
	for(int i=0;i<=n;i++)f[i]=rd()%p;
	for(int i=0;i<=m;i++)g[i]=rd()%p;
	a=poly(f,n+1);b=poly(g,m+1);c=a*b;
	for(int i=0;i<c.n;i++)printf("%d ",c[i]);
	return 0;
}

评测结果