代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=998244353;
const int gen=3;
const int N=1<<21|5;
inline ll fsp(ll x,ll y){
	ll ans=1;for(;y;y>>=1,x=x*x%mod)(y&1)&&(ans=ans*x%mod);
	return ans;
}namespace Math{
	int initdw=2,initdinv=2,w[N],iv[N];
	inline void initw(int x){
		(!w[1])&&(w[1]=1);
		for(int k=initdw;k<x;k<<=1){
			w[k]=1;w[k+1]=fsp(3,(mod-1)/(k<<1));
			for(int i=2;i<k;i++)w[i+k]=1ll*w[i+k-1]*w[k+1]%mod;
		}initdw=max(initdw,x);
	}inline void initinv(int x){
		(!iv[1])&&(iv[1]=1);
		for(int i=initdinv;i<=x;i++)iv[i]=1ll*(mod-mod/i)*iv[mod%i]%mod;
		initdinv=max(x+1,initdinv);
	}inline ll ginv(ll x){
		(x<(1<<21))&&(initinv(x),0);
		return x<initdinv?iv[x]:fsp(x,mod-2);
	}inline void ntt(int *a,int lim,bool fl=1){
		static int rev[N];static unsigned ll A[N];initw(lim);
		for(int i=0;i<lim;i++){A[rev[i]=rev[i>>1]>>1|((i&1)?lim>>1:0)]=a[i];}
		for(int k=1;k<lim;k<<=1)for(int j=0;j<lim;j+=k<<1)
			for(int i=j,t;i<j+k;i++){t=A[i+k]*w[i-j+k]%mod;A[i+k]=A[i]+mod-t,A[i]+=t;}
		for(int i=0;i<lim;i++)a[i]=A[i]%mod;
		if(!fl){reverse(a+1,a+lim);for(int i=0,niv=ginv(lim);i<lim;i++)a[i]=1ll*niv*a[i]%mod;}
	}
}namespace Poly{
	using Math::ntt;
	#define vc vector<int>
	int B[N];
	struct poly{
		vc f;poly(int x=0){f.clear();(x)&&(f.push_back(x),0);}
		poly(int *a,int n){f.resize(n);memcpy(f.data(),a,n<<2);}
		inline int size()const{return f.size();}inline void resize(int x){return f.resize(x);}
		inline int* data(){return f.data();}inline const int* data()const{return f.data();}
		inline int operator[](int x)const{return x<size()?f.at(x):0;}inline int& operator[](int x){return f.at(x);}
		inline void copy(int *a,int len){
			memcpy(a,f.data(),min(len,size())<<2);
			(size()<len)&&(memset(a+size(),0,len-size()<<2),0);
		}inline poly& operator *=(const poly& a){
			int lim=1;while(lim<a.size()+size()-1)lim<<=1;
			f.resize(lim);memcpy(B,a.data(),a.size()<<2);
			ntt(f.data(),lim);ntt(B,lim);for(int i=0;i<lim;i++)f[i]=1ll*f[i]*B[i]%mod;
			ntt(f.data(),lim,0);memset(B,0,lim<<2);return *this;
		}inline poly operator *(const poly& a){poly b(*this);(b*=a).resize(size()+a.size()-1);return b;}
		inline void print(char ch=' '){
			for(int i=0;i<size();i++,putchar(ch))printf("%d",f[i]);
			putchar('\n');
		}
	};
}
using Poly::poly;
int n,m,a[N],b[N];
poly f;
int 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);
	(poly(a,n)*poly(b,m)).print();
	return 0;
}

评测结果