代码

#include<bits/stdc++.h>
#define ll long long
#define vci vector<int>
using namespace std;
const int mod=998244353;
const int N=1<<21|5;
const int gen=3;
inline int fsp(int x,int y){
	int ans=1;for(;y;y>>=1,x=1ll*x*x%mod)(y&1)&&(ans=1ll*ans*x%mod);
	return ans;
}namespace Math{
	int tr=0,tw=2,tv=2,rev[N],w[N],iv[N];
	inline void initrev(int x){
		tr=x;for(int i=0;i<x;i++)rev[i]=rev[i>>1]>>1|((i&1)?x>>1:0);
	}inline void initw(int x){(!w[1])&&(w[1]=1);
		for(;tw<x;tw<<=1){
			w[tw]=1;w[tw+1]=fsp(gen,mod/(tw<<1));
			for(int i=tw+2;i<(tw<<1);++i)w[i]=1ll*w[i-1]*w[tw+1]%mod;
		}
	}inline void initiv(int x){(!iv[1])&&(iv[1]=1);
		for(;tv<=x;++tv)iv[tv]=1ll*(mod-mod/tv)*iv[mod%tv]%mod;
	}inline int ginv(int x){
		(x<=1<<21)&&(initiv(x),0);
		return x<tv?iv[x]:fsp(x,mod-2);
	}inline void ntt(int* a,int lim,int fl=1){
		static unsigned ll A[N];initw(lim);
		(tr!=lim)&&(initrev(lim),0);
		for(int i=0;i<lim;i++)A[rev[i]]=a[i];
		for(int k=1;k<lim;k<<=1){
			if(k==1<<18)for(int i=0;i<lim;++i)A[i]%=mod;
			for(int j=0;j<lim;j+=k<<1)for(int i=j,t;i<j+k;++i)
				A[i+k]=A[i]+mod-(t=A[i+k]*w[i+k-j]%mod),A[i]+=t;
		}if(fl^1){reverse(A+1,A+lim);for(int i=0,niv=ginv(lim);i<lim;i++)a[i]=A[i]*niv%mod;}
		else for(int i=0;i<lim;i++)a[i]=A[i]%mod;
	}
}namespace Poly{
	using Math::ntt;
	using Math::ginv;
	int A[N],B[N],C[N];
	struct poly{
		vci 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 operator [](int x)const{return x<f.size()?f[x]:0;}
		inline int& operator [](int x){return f.at(x);}
		inline int* data(){return f.data();}inline const int* data()const{return f.data();}
		inline int size()const{return f.size();}inline void resize(int x){return f.resize(x);}
		inline void copy(int *a,int len)const{
			memcpy(a,data(),min(len,size())<<2);
			(len>size())&&(memset(a+size(),0,len-size()<<2));
		}inline void print(char ch=' ')const{
			for(int i=0;i<size();++i,putchar(ch))printf("%d",f[i]);putchar('\n');
		}inline poly slice(int len)const{poly a;a.resize(len);copy(a.data(),len);return a;}
		inline poly& operator +=(const poly& a){
			(a.size()>size())&&(resize(a.size()),0);
			for(int i=0;i<a.size();i++)f[i]=(f[i]+a[i])%mod;
			return *this;
		}inline poly& operator -=(const poly& a){
			(a.size()>size())&&(resize(a.size()),0);
			for(int i=0;i<a.size();i++)f[i]=(f[i]+mod-a[i])%mod;
			return *this;
		}inline poly operator +(const poly& a)const{poly b(*this);return b+=a;}
		inline poly operator -(const poly& a)const{poly b(*this);return b-=a;}
		inline poly& operator *=(const poly& a){
			int lim=1;while(lim<size()+a.size()-1)lim<<=1;
			resize(lim);memcpy(A,a.data(),a.size()<<2);ntt(data(),lim);ntt(A,lim);
			for(int i=0;i<lim;i++)f[i]=1ll*f[i]*A[i]%mod;
			ntt(data(),lim,0);memset(A,0,lim<<2);return *this;
		}inline poly operator *(const poly& a)const{poly b(*this);(b*=a).resize(size()+a.size()-1);return b;}
		inline poly mul(const poly& a)const{poly b(*this);(b*=a.slice(size())).resize(size());return b;}
		inline poly inv(int x=-1)const{
			poly a(ginv(f[0]));(~x)||(x=size());
			for(int i=1;i<x;i<<=1){
				memcpy(A,a.data(),i<<2);copy(B,i<<1);
				a.resize(i<<1);ntt(A,i<<1);ntt(B,i<<1);
				for(int j=0;j<(i<<1);j++)B[j]=mod-1ll*A[j]*B[j]%mod;
				ntt(B,i<<1,0);memset(B,0,i<<2);ntt(B,i<<1);
				for(int j=0;j<(i<<1);j++)B[j]=1ll*A[j]*B[j]%mod;
				ntt(B,i<<1,0);memcpy(a.data()+i,B+i,i<<2);
				((i<<1)<x)||(memset(A,0,i<<3),memset(B,0,i<<3),0);
			}a.resize(x);return a;
		}
		inline poly div(const poly& a)const{
			int len=1;while(len<size())len<<=1;
			poly b(a.inv(len>>1));b.copy(A,len);copy(B,len>>1);
			ntt(A,len);ntt(B,len);for(int i=0;i<len;i++)B[i]=1ll*A[i]*B[i]%mod;
			ntt(B,len,0);memset(B+(len>>1),0,len<<1);
			ntt(B,len);a.copy(C,len);ntt(C,len);
			for(int i=0;i<len;i++)B[i]=1ll*B[i]*C[i]%mod;
			ntt(B,len,0);memset(B,0,len<<1);ntt(B,len);
			for(int i=0;i<len;i++)B[i]=mod-1ll*A[i]*B[i]%mod;
			ntt(B,len,0);b.resize(len);memcpy(b.data()+(len>>1),B+(len>>1),len<<1);
			b.resize(size());return b;
		}inline poly der()const{
			poly a;a.resize(size()-1);
			for(int i=1;i<=a.size();i++)a[i-1]=1ll*i*f[i]%mod;
			return a;
		}inline poly ite()const{
			poly a;a.resize(size()+1);
			for(int i=size();i;i--)a[i]=1ll*ginv(i)*f[i-1]%mod;
			return a;
		}inline poly ln()const{return der().div(*this).ite();}
		inline poly exp(int x=-1)const{
			poly a(1);(~x)||(x=size());
			for(int i=1;i<x;i<<=1){a.resize(i<<1);a-=a.mul(a.ln()-slice(i<<1));}
			a.resize(x);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(a,n)*poly(b,m)).print();
	return 0;
}

评测结果