代码

// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,gen=3;
namespace math{
#ifdef DEBUG
#ifndef need_butterfly
	#define need_butterfly
#endif
#endif
	// fast power , (x and ans) must in [-mod,mod], y must in [-mod+1,mod-1] 
	typedef int i32;
	typedef unsigned int u32;
	typedef long long i64;
	typedef unsigned long long u64;
	template<typename T=int>
	inline T fsp(i64 x,int y,i64 ans=1){
		for(y<0?y+=mod-1:0;y;y>>=1,x=x*x%mod)
			y&1?ans=ans*x%mod:0;
		return ans;
	}
	inline int lg(int x){return x==0?-1:__lg(x);}
	namespace fast_number_theory_transform{
		const int maxbit=22;
		const u32 modm2=mod+mod;
		template<class T>
		inline void butterfly(T* p,int bit) {
			for(u32 i=0,j=0;i<(1u<<bit);i++){
				if(i>j)swap(p[i],p[j]);
				for(u32 l=1u<<(bit-1);(j^=l)<l;l>>=1);
			}
		}
		u32 *_p0[maxbit+1],*_p1[maxbit+1];
		inline void prep(int bit){
			static int k=0;
			for(;k<bit;k++){
				u32 *p,*q,nl=1<<k;
				
				u64 g=fsp(3,mod>>(k+1));
				p=_p0[k]=new u32[nl<<1];q=p+nl;
				for(int i=p[0]=1;i<nl;i++)p[i]=p[i-1]*g%mod;
				for(int i=0;i<nl;i++)q[i]=(u64(p[i])<<32)/mod;

				g=fsp(g,-1);
				p=_p1[k]=new u32[nl<<1];q=p+nl;
				for(int i=p[0]=1;i<nl;i++)p[i]=p[i-1]*g%mod;
				for(int i=0;i<nl;i++)q[i]=(u64(p[i])<<32)/mod;
			}
		}inline u32 ntt_mul(u32 x,u32 p,u64 q){return x*p-(u32)(q*x>>32)*mod;}
		void ntt(u32* a,int bit){
			prep(bit);
			for(int k=bit;k-->0;){
				u32 *_p=_p0[k],*_q=_p+(1<<k);
				u32 *_a0=a,*_a1=a+(1<<k);
				for(int i=0;i<1<<(bit-k-1);i++,_a0+=1<<(k+1),_a1+=1<<(k+1))
					for(int j=0;j<(1<<k);++j){
						u32 x=_a0[j],y=_a1[j];
						_a0[j]=x+y-(x+y>=modm2)*modm2;
						_a1[j]=ntt_mul(x+modm2-y,_p[j],_q[j]);
					}
			}for(int i=0;i<(1<<bit);i++){
				a[i]-=(a[i]>=modm2)*modm2;
				a[i]-=(a[i]>=mod)*mod;
			}
		#ifdef need_butterfly
			butterfly(a,bit);
		#endif
		}
		
		void intt(u32* a,int bit){
			prep(bit);
		#ifdef need_butterfly
			butterfly(a,bit);
		#endif
			for(int k=0;k<bit;k++){
				u32 *_p=_p1[k],*_q=_p+(1<<k);
				u32 *_a0=a,*_a1=a+(1<<k);
				for(int i=0;i<1<<(bit-k-1);i++,_a0+=1<<(k+1),_a1+=1<<(k+1))
					for(int j=0;j<(1<<k);++j){
						u32 x=_a0[j]-(_a0[j]>=modm2)*modm2,y=ntt_mul(_a1[j],_p[j],_q[j]);
						_a0[j]=x+y;_a1[j]=x+modm2-y;
					}
			}
			u64 iv=mod;iv<<=bit;iv=(iv-mod+1)>>bit;
			for(int i=0;i<(1<<bit);i++)
				a[i]=a[i]*iv%mod;
		}
	}using fast_number_theory_transform::ntt;
	using fast_number_theory_transform::intt;
}
namespace polynormial{
	typedef int i32;
	typedef unsigned int u32;
	typedef long long i64;
	typedef unsigned long long u64;
	typedef vector<u32> vec;
	using math::lg;
	// using math::fsp;
	using math::ntt;
	using math::intt;
	struct poly{
		vec f;
		
		poly(u32 x=0):f(1){f[0]=x;}
		poly(int x):f(1){f[0]=x+((x>>31)&mod);}
		poly(const vec& _f):f(_f){}
		poly(const vector<int>& _f){
			f.resize(f.size());
			for(int i=0;i<_f.size();i++){
				f[i]=_f[i]+((_f[i]>>31)&mod);
			}
		}
		poly(initializer_list<u32>_f):f(_f){}
		poly(initializer_list<int>_f){
			f.resize(_f.size());
			int i=0;for(int x:_f){
				f[i++]=x+((x>>31)&mod);
			}
		}
		template<typename T>
		poly(T __first,T __last):
			poly(vector<typename iterator_traits<T>::value_type>(__first,__last)){}
		
		inline operator vec()const{return f;}
		inline void swap(poly& _f){f.swap(_f.f);}
		inline int degree()const{return f.size()-1;}
		inline poly& redegree(int x){return f.resize(x+1),*this;}
		inline void clear(){f.resize(1);f[0]=0;}
		inline void shrink(){
			int ndeg=f.size()-1;
			while(ndeg>0&&f[ndeg]==0)ndeg--;
			f.resize(ndeg+1);
		}
		// inline size_t size() const{return f.size();}
		// inline void resize(int x){return f.resize(x);}
		
		// get the the pre [0,n]  
		inline poly slice(int n)const{
			return n<0?poly(0):(n<f.size()?poly(f.begin(),f.begin()+n+1):poly(*this).redegree(n));
		}

		inline u32& operator [](int x){
		#ifdef DEBUG
			return f.at(x);
		#else
			return f[x];
		#endif
		}
		inline u32 operator [](int x)const{
		#ifdef DEBUG
			return f.at(x);
		#else
			return f[x];
		#endif
		}

		inline u32* data(){return f.data();}
		inline const u32* data()const{return f.data();}

		// redegree to max(this->degree(),a.degree())
		inline poly& operator +=(const poly& a){
			f.resize(max(f.size(),a.f.size()));
			for(int i=0;i<a.f.size();i++)f[i]=f[i]+a.f[i]-(f[i]+a.f[i]>=mod)*mod;
			return *this;
		}
		// redegree to max(this->degree(),a.degree())
		inline poly& operator -=(const poly& a){
			f.resize(max(f.size(),a.f.size()));
			for(int i=0;i<a.f.size();i++)f[i]=f[i]-a.f[i]+(f[i]<a.f[i])*mod;
			return *this;
		}
		// redegree to max(this->degree(),a.degree())
		inline poly operator +(const poly& a)const{return (poly(*this)+=a);}
		// redegree to max(this->degree(),a.degree())
		inline poly operator -(const poly& a)const{return (poly(*this)-=a);}

		// redegree to this->degree()
		inline poly operator -()const{
			poly _f;_f.f.resize(f.size());
			for(int i=0;i<_f.f.size();i++)
				_f.f[i]=mod-f[i];
			return _f;
		}

		// redegree to this->degree()
		inline poly& pluswith(const poly& a){
			for(int i=0,i_up=min(f.size(),a.f.size());i<i_up;i++)
				f[i]=f[i]+a.f[i]-(f[i]+a.f[i]>=mod)*mod;
			return *this;
		}
		// redegree to this->degree()
		inline poly plus(const poly& a)const{return (poly(*this).pluswith(a));}
		// redegree to this->degree()
		inline poly& minuswith(const poly& a){
			for(int i=0,i_up=min(f.size(),a.f.size());i<i_up;i++)
				f[i]=f[i]-a.f[i]+(f[i]<a.f[i])*mod;
			return *this;
		}
		// redegree to this->degree()
		inline poly minus(const poly& a)const{return (poly(*this).minuswith(a));}

 		// redegree to this->degree()+a.degree() 
		inline poly& operator *=(const poly& a){
			int n=degree(),m=a.degree();
			if(n<16||m<16){
				f.resize(n+m+1);
				for(int i=n+m;i>=0;i--){
					f[i]=1ll*f[i]*a.f[0]%mod;
					for(int j=max(1,i-n),j_up=min(m,i);j<=j_up;j++)
						f[i]=(f[i]+1ll*f[i-j]*a.f[j])%mod;
				}return *this;
			}
			vec _f(a.f);
			int bit=lg(n+m)+1;
			f.resize(1<<bit);_f.resize(1<<bit);
			ntt(f.data(),bit);ntt(_f.data(),bit);
			for(int i=0;i<(1<<bit);i++)f[i]=1ll*f[i]*_f[i]%mod;
			intt(f.data(),bit);f.resize(n+m+1);
			return *this;
		}
 		// redegree to this->degree()+a.degree() 
		inline poly operator *(const poly& a)const{return (poly(*this)*=a);}

		// redegree to this->degree()
		inline poly& multiplywith(const poly& a){
			int n=degree(),m=a.degree();
			if(n<16||m<16){
				for(int i=n;i>=0;i--){
					f[i]=1ll*f[i]*a.f[0]%mod;
					for(int j=max(1,i-n),j_up=min(m,i);j<=j_up;j++)
						f[i]=(f[i]+1ll*f[i-j]*a.f[j])%mod;
				}return *this;
			}
			vec _f(a.f);
			int bit=lg(n+m)+1;
			f.resize(1<<bit);_f.resize(1<<bit);
			ntt(f.data(),bit);ntt(_f.data(),bit);
			for(int i=0;i<(1<<bit);i++)f[i]=1ll*f[i]*_f[i]%mod;
			intt(f.data(),bit);f.resize(n+1);
			return *this;
		}
		// redegree to this->degree()
		inline poly multiply(const poly& a)const{return (poly(*this).multiplywith(a));}

		// redegree to this->degree() + x, x must int [0,inf]
		inline poly& operator <<=(int x){
			return f.resize(f.size()+x),memmove(f.data()+x,f.data(),4*(f.size()-x)),
				memset(f.data(),0,4*x),*this;
		}
		// redegree to this->degree() - x, x must int [0,inf]
		inline poly operator <<(int x)const{return (poly(*this)<<=x);}
		
		// redegree to this->degree() - x, x must int [0,inf]
		inline poly& operator >>=(int x){
			return x>=f.size()?(clear(),*this):
				(memmove(f.data(),f.data()+x,4*(f.size()-x)),f.resize(f.size()-x),*this);
		}
		// redegree to this->degree() - x, x must int [0,inf]
		inline poly operator >>(int x)const{return (poly(*this)>>=x);}

		// redegree to this->degree()
		inline poly& shiftindexwith(int x){
			return x>=f.size()?(memset(f.data(),0,4*f.size()),*this):
				(memmove(f.data(),f.data()+x,4*(f.size()-x)),memset(f.data(),0,4*x),*this);
		}
		// redegree to this->degree()
		inline poly shiftindex(int x)const{return (poly(*this).shiftindexwith(x));}
		// redegree to this->degree()
		// inline poly inv()const{
		// 	vec a(1);a[0]=fsp(f[0],-1);
		// 	for(int nb=0;(1<<nb)<f.size();nb++){

		// 	}
		// }
	};
	
	ostream& operator <<(ostream& out,const poly& x){
		out<<x.f[0];
		for(int i=1;i<x.f.size();i++)out<<' '<<x.f[i];
		return out;
	}
}
// using math::fsp;
using polynormial::poly;
int n,m;
unsigned a[262144],b[262144];
int main(){
#ifndef DEBUG
	ios::sync_with_stdio(0);
	cin.tie(0);
#endif
	cin>>n>>m;
	for(int i=0;i<=n;i++)cin>>a[i];
	for(int i=0;i<=m;i++)cin>>b[i];
	cout<<(poly(a,a+n+1)*=poly(b,b+m+1))<<endl;
}

评测结果