代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define N (1<<18)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define putchar(c) (o1==o2?(fwrite(clt,1,1<<20,stdout),o1=clt,*o1++=c):(*o1++=c))
char buf[1<<20],*p1=buf,*p2=buf,clt[1<<20],*o1=clt,*o2=clt+(1<<20);
int read(){
	int w=0,f=1;
	char c=' ';
	while(c<'0'||c>'9')c=getchar(),f=c=='-'?-1:f;
	while(c>='0'&&c<='9')w=w*10+c-48,c=getchar();
	return w*f;
}
void print(int x){
	if(!x)putchar(48);
	else{
		int d[11];
		for(d[0]=0;x;d[++d[0]]=x%10,x/=10);
		for(;d[0];putchar(d[d[0]--]^48));
	}
}
const int mod=998244353,G=3,iG=332748118,inv2=499122177;
int modread(){
	int w=0,f=1;
	char c=' ';
	while(c<'0'||c>'9')c=getchar(),f=c=='-'?-1:f;
	while(c>='0'&&c<='9')w=(w*10+c-48)%mod,c=getchar();
	return w*f;
}
int pown(int x,int y){
	int res=1;
	while(y){
		if(y&1)res=res*x%mod;
		x=x*x%mod,y>>=1;
	}
	return res;
}
int rev[N],pg[N],lainit,fac[N+5],ifac[N+5],inv[N+5],dft[N<<1];
ull tmp[N];
void init(int lim){
	lim+=5,fac[0]=1;
	for(int i=1;i<lim;i++)
		fac[i]=fac[i-1]*i%mod;
	ifac[lim-1]=pown(fac[lim-1],mod-2);
	for(int i=lim-1;i>0;i--)
		ifac[i-1]=ifac[i]*i%mod;
	for(int i=1;i<lim;i++)
		inv[i]=ifac[i]*fac[i-1]%mod;
}
void init_NTT(int lim,int lg){
	if(lim==lainit||!lg)return;
	lainit=lim;
	for(int i=0;i<lim;i++)
		rev[i]=(rev[i>>1]>>1)|((i&1)<<(lg-1));
	int w=pown(G,(mod-1)/lim);
	pg[lim>>1]=1;
	for(int i=(lim>>1)+1;i<lim;i++)
		pg[i]=pg[i-1]*w%mod;
	for(int i=(lim>>1)-1;i;i--)
		pg[i]=pg[i<<1];
}
void NTT(int*a,int lim,int lg,int op){
	init_NTT(lim,lg);
	if(op)reverse(a+1,a+lim);
	for(int i=0;i<lim;i++)
		tmp[rev[i]]=a[i];
	for(int i=1,len=2;i<lim;i<<=1,len<<=1){
		for(int j=0;j<lim;j+=len)
			for(int k=0;k<i;k++){
				int x=tmp[i+j+k]*pg[i+k]%mod;
				tmp[i+j+k]=tmp[j+k]+mod-x,tmp[j+k]+=x;
			}
		if(lg<=18||len!=(1<<18))continue;
		for(int j=0;j<lim;j++)
			tmp[j]%=mod;
	}
	if(!op){
		for(int i=0;i<lim;i++)
			a[i]=tmp[i]%mod;
		return;		
	}
	int ilim=mod-(mod-1)/lim;
	for(int i=0;i<lim;i++)
		a[i]=tmp[i]*ilim%mod;
}//1E(n)
void polymul(int*a,int*b,int lim,int lg,int op=0){
	if(lim<=16){
		ull c[16];
		for(int i=0,_i=op?lim:(lim>>1);i<_i;i++){
			c[i]=0;
			for(int j=0;j<=i;j++)
				c[i]+=a[j]*b[i-j];
		}
		for(int i=0,_i=op?lim:(lim>>1);i<_i;i++)
			a[i]=c[i]%mod;
		return;
	}
	if(lim<=64){
		ull c[64];
		for(int i=0,_i=op?lim:(lim>>1);i<_i;i++){
			c[i]=0;
			for(int j=0;j<=(i>>4);j++,c[i]%=mod)
				for(int k=(j<<4),l=min(j<<4|15,i);k<=l;k++)
					c[i]+=a[k]*b[i-k];
		}
		memcpy(a,c,sizeof(int)*(op?lim:(lim>>1)));
		return;
	}
	NTT(a,lim,lg,0),NTT(b,lim,lg,0);
	for(int i=0;i<lim;i++)
		a[i]=a[i]*b[i]%mod;
	NTT(a,lim,lg,1);
	if(op)return;
	memset(a+(lim>>1),0,sizeof(int)*(lim>>1));
	memset(b,0,sizeof(int)*lim);
}//3E(n+m)
int pl1[N],pl2[N],pl3[N],pl4[N],pl5[N],pl6[N],pl7[N],pl8[N];
void init_dft(int*a,int*b,int x,int lim){
	for(int i=1<<x,Lg=x;i<=lim;i<<=1,Lg++){
		memcpy(b,a,sizeof(int)*i);
		NTT(b,i,Lg,0);
		memcpy(dft+i,b,sizeof(int)*i);
	}
	memset(b,0,sizeof(int)*lim);
}//2E(n)
void polyinv_slow(int*a,int lim,int lg){
	pl1[0]=pown(a[0],mod-2);
	for(int i=1,len=2,Lg=1;i<lim;i<<=1,len<<=1,Lg++){
		memcpy(pl2,pl1,sizeof(int)*i);
		memcpy(pl3,a,sizeof(int)*len);
		polymul(pl2,pl3,len,Lg,1);
		memset(pl2,0,sizeof(int)*i);
		memcpy(pl3,pl1,sizeof(int)*len);
		polymul(pl2,pl3,len,Lg,1);
		for(int j=i;j<len;j++)
			pl1[j]=(pl1[j]*2-pl2[j]+mod)%mod;
	}
	memcpy(a,pl1,sizeof(int)*lim);
	memset(pl1,0,sizeof(int)*lim);
	memset(pl2,0,sizeof(int)*lim);
	memset(pl3,0,sizeof(int)*lim);
}//12E(n)
void polyinv(int*a,int lim,int lg){
	pl1[0]=pown(a[0],mod-2);
	for(int i=1,len=2,Lg=1;i<lim;i<<=1,len<<=1,Lg++){
		memcpy(pl2,pl1,sizeof(int)*i);
		memcpy(pl3,a,sizeof(int)*len);
		NTT(pl2,len,Lg,0),NTT(pl3,len,Lg,0);
		for(int j=0;j<len;j++)
			pl3[j]=pl3[j]*pl2[j]%mod;
		NTT(pl3,len,Lg,1);
		memset(pl3,0,sizeof(int)*i);
		NTT(pl3,len,Lg,0);
		for(int j=0;j<len;j++)
			pl3[j]=pl3[j]*pl2[j]%mod;
		NTT(pl3,len,Lg,1);
		for(int j=i;j<len;j++)
			pl1[j]=(mod-pl3[j])%mod;
	}
	memcpy(a,pl1,sizeof(int)*lim);
	memset(pl1,0,sizeof(int)*lim);
	memset(pl2,0,sizeof(int)*lim);
	memset(pl3,0,sizeof(int)*lim);
}//10E(n)
void polyder(int*a,int lim){
	for(int i=1;i<lim;i++)
		a[i-1]=a[i]*i%mod;
	a[lim-1]=0;
}
void polyider(int*a,int lim){
	for(int i=lim-1;i;i--)
		a[i]=a[i-1]*inv[i]%mod;
	a[0]=0;
}
void polyln(int*a,int lim,int lg){
	memcpy(pl4,a,sizeof(int)*lim);
	polyinv(pl4,lim,lg);
	polyder(a,lim);
	polymul(a,pl4,lim<<1,lg+1);
	polyider(a,lim);
	memset(pl4,0,sizeof(int)*lim);
}//16E(n)
void polysqrt(int*a,int lim,int lg){
	pl6[0]=1;
	for(int i=1,len=2,Lg=1;i<=lim;i<<=1,len<<=1,Lg++){
		memcpy(pl5,a,sizeof(int)*i);
		memcpy(pl4,pl6,sizeof(int)*i);
		polyinv(pl4,i,Lg-1);
		polymul(pl5,pl4,len,Lg);
		for(int j=0;j<i;j++)
			pl6[j]=(pl6[j]+pl5[j])*inv2%mod;
	}
	memcpy(a,pl5,sizeof(int)*lim);
	for(int i=(lim>>1);i<lim;i++)
		a[i]=a[i]*inv2%mod;
	memset(pl4,0,sizeof(int)*lim);
	memset(pl5,0,sizeof(int)*lim);
	memset(pl6,0,sizeof(int)*lim);
}//32E(n)
void polyexp_slow(int*a,int lim,int lg){
	pl5[0]=1;
	for(int i=1,len=2,Lg=1;i<lim;i<<=1,len<<=1,Lg++){
		memcpy(pl6,pl5,sizeof(int)*i);
		polyln(pl6,len,Lg);
		for(int j=0;j<len;j++)
			pl6[j]=(a[j]-pl6[j]+mod)%mod;
		memcpy(pl4,pl5,sizeof(int)*i);
		polymul(pl6,pl4,len,Lg,1);
		memset(pl4,0,sizeof(int)*len);
		memcpy(pl5+i,pl6+i,sizeof(int)*i);
	}
	memcpy(a,pl5,sizeof(int)*lim);
	memset(pl5,0,sizeof(int)*lim);
	memset(pl6,0,sizeof(int)*lim);
}//38E(n)
void polyexp(int*a,int lim,int lg){
	pl4[0]=1;
	polyder(a,lim);
	for(int i=1,len=2,Lg=1;i<lim;i<<=1,len<<=1,Lg++){
		memcpy(pl5,pl4,sizeof(int)*i);
		memcpy(pl6,pl4,sizeof(int)*i);
		memcpy(pl7,pl4,sizeof(int)*i);
		polyder(pl5,i);
		polyinv(pl6,i,Lg-1);
		NTT(pl5,i,Lg-1,0),NTT(pl6,i,Lg-1,0),NTT(pl7,i,Lg-1,0);
		for(int j=0;j<i;j++)
			pl5[j]=pl5[j]*pl6[j]%mod,pl7[j]=pl7[j]*pl6[j]%mod;
		NTT(pl5,i,Lg-1,1),NTT(pl7,i,Lg-1,1),pl7[0]=(pl7[0]-1+mod)%mod;
		for(int j=0;j<i;j++)
			pl5[j]=(pl5[j]-a[j]-a[j+i]+mod*2)%mod,pl6[j]=a[j];
		pl5[i-1]=(pl5[i-1]+a[len-1])%mod,pl6[i-1]=0;
		polymul(pl6,pl7,len,Lg);
		pl6[i]=0,pl8[i-1]=pl5[i-1];
		for(int j=i;j<len-1;j++)
			pl8[j]=(pl5[j-i]-pl6[j-i]+mod)%mod;
		polyider(pl8,len);
		for(int j=0;j<i;j++)
			pl8[j]=pl8[j+i];
		memset(pl8+i,0,sizeof(int)*i);
		memcpy(pl5,pl4,sizeof(int)*i);
		memset(pl5+i,0,sizeof(int)*i);
		polymul(pl8,pl5,len,Lg);
		for(int j=i;j<len;j++)
			pl8[j]=pl8[j-i],pl4[j]=(mod-pl8[j])%mod;
		memset(pl8,0,sizeof(int)*i);
	}
	memcpy(a,pl4,sizeof(int)*lim);
	memset(pl4,0,sizeof(int)*lim);
	memset(pl5,0,sizeof(int)*lim);
	memset(pl6,0,sizeof(int)*lim);
	memset(pl7,0,sizeof(int)*lim);
	memset(pl8,0,sizeof(int)*lim);
}//27E(n)
void polyexp_cdq_solve(int l,int r,int lg){
	if(r-l<=64){
		ull c[64];
		for(int i=0;i<r-l;i++){
			c[i]=0;
			for(int j=0;j<=(i>>4);j++,c[i]%=mod)
				for(int k=(j<<4),u=min(j<<4|15,i-1);k<=u;k++)
					c[i]+=pl2[l+k]*pl1[i-k];
			pl2[l+i]=l+i?(pl2[l+i]+c[i])*inv[l+i]%mod:1;
		}
		return;
	}
	int mid=(l+r)>>1;
	polyexp_cdq_solve(l,mid,lg-1);
	memcpy(pl3,pl2+l,sizeof(int)*((r-l)/2));
	memset(pl3+(r-l)/2,0,sizeof(int)*((r-l)/2));
	NTT(pl3,r-l,lg,0);
	for(int i=0;i<r-l;i++)
		pl3[i]=pl3[i]*dft[r-l+i]%mod;
	NTT(pl3,r-l,lg,1);
	for(int i=(r-l)/2;i<r-l;i++)
		pl2[l+i]=(pl2[l+i]+pl3[i])%mod;
	polyexp_cdq_solve(mid,r,lg-1);
}
void polyexp_cdq(int*a,int lim,int lg){
	memcpy(pl1,a,sizeof(int)*lim);
	for(int i=0;i<lim;i++)
		pl1[i]=pl1[i]*i%mod;
	init_dft(pl1,pl2,7,lim);
	polyexp_cdq_solve(0,lim,lg);
	memcpy(a,pl2,sizeof(int)*lim);
	memset(pl1,0,sizeof(int)*lim);
	memset(pl2,0,sizeof(int)*lim);
	memset(pl3,0,sizeof(int)*lim);
}
void polydivmod(int*a,int*b,int len1,int len2){
	for(int i=0;i<=len1;i++)
		pl4[i]=a[len1-i];
	for(int i=0;i<=min(len1-len2,len2);i++)
		pl5[i]=b[len2-i];
	int lim=1,lg=0;
	for(;lim<=len1-len2;lg++,lim<<=1);
	polyinv(pl5,lim,lg);
	for(lim=1,lg=0;lim<=(len1<<1);lg++,lim<<=1);
	polymul(pl4,pl5,lim,lg);
	reverse(pl4,pl4+len1-len2+1);
	memcpy(pl5,a,sizeof(int)*(len1+1));
	memcpy(a,pl4,sizeof(int)*(len1-len2+1));
	memset(a+len1-len2+1,0,sizeof(int)*len2);
	memset(pl4+len1-len2+1,0,sizeof(int)*((lim>>1)-len1+len2-1));
	for(lim=1,lg=0;lim<=len1;lg++,lim<<=1);
	polymul(b,pl4,lim,lg,1);
	for(int i=0;i<len2;i++)
		b[i]=(pl5[i]+mod-b[i])%mod;
	memset(pl4,0,sizeof(int)*lim);
	memset(b+len2,0,sizeof(int)*(lim-len2));
	for(lim=1,lg=0;lim<=(len1<<1);lg++,lim<<=1);
	memset(pl5,0,sizeof(int)*(lim>>1));
}//10E(n-m)+9E(n)
void polypown(int*a,int k,int lim,int lg){
	polyln(a,lim,lg);
	for(int i=0;i<lim;i++)
		a[i]=a[i]*k%mod;
	polyexp_cdq(a,lim,lg);
}//43E(n)
int n,m,A[N],B[N];
signed main(){
	n=read(),m=read();
	for(int i=0;i<=n;i++)
		A[i]=read();
	for(int i=0;i<=m;i++)
		B[i]=read();
	int lim=1,lg=0;
	for(;lim<=n+m;lg++,lim<<=1);
	polymul(A,B,lim,lg,1);
	for(int i=0;i<=n+m;i++)
		print(A[i]),putchar(i==n+m?'\n':' ');
	fwrite(clt,1,o1-clt,stdout);
	return 0;
}

评测结果