代码

#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,initdw<<=1){
			w[k]=1;w[k+1]=fsp(gen,mod/(k<<1));
			for(int i=2;i<k;++i)w[i+k]=(ll)w[i+k-1]*w[k+1]%mod;
		}
	}inline void initinv(int x){
		(!iv[1])&&(iv[1]=1);
		for(int i=initdinv;i<=x;i++)iv[i]=(ll)(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>
	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 void print(char ch=' '){
			for(int i=0;i<size();i++,putchar(ch))printf("%d",f[i]);
			putchar('\n');
		}
	};
	poly Mul(poly a,poly b){
		int lim=1,now=a.size()+b.size()-1;while(lim<now)lim<<=1;
		a.resize(lim);b.resize(lim);ntt(a.data(),lim);ntt(b.data(),lim);
		for(int i=0;i<lim;i++)a[i]=1ll*a[i]*b[i]%mod;ntt(a.data(),lim,0);
		a.resize(now);return a;
	}
}
using Poly::poly;
int n,m,a[N],b[N];
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::Mul(poly(a,n),poly(b,m)).print();
	return 0;
}

评测结果