代码

#include<bits/stdc++.h>
using namespace std; 
const int N=21e5+3,P=998244353;
int n,r[N],a[N],b[N],w[N];
int qp(int a,int b){
	int r=1;
	for(;b;b>>=1,a=a*1ll*a%P)if(b&1)r=r*1ll*a%P;
	return r;
}
void pre(int m){
	int i,j,g;
	for(n=1;n<=m;n<<=1);
	for(i=0,w[j=n>>1]=1;i<n;++i)r[i]=(r[i>>1]>>1)|((i&1)?j:0);
	for(i=j+1,g=qp(3,(P-1)/n);i<n;++i)w[i]=w[i-1]*1ll*g%P;
	for(i=j-1;i>0;--i)w[i]=w[i<<1];
}
void ntt(int*a,bool b=0){
	int i,j,k,x,*g,*u,*v;
	for(i=0;i<n;++i)if(i<r[i])swap(a[i],a[r[i]]);
	for(i=1;i<n;i<<=1)for(j=0;j<n;j+=i<<1)for(k=0,g=w+i,u=a+j,v=u+i;k<i;++k)
	x=g[k]*1ll*v[k]%P,v[k]=u[k]<x?u[k]-x+P:u[k]-x,u[k]=(u[k]+=x)<P?u[k]:u[k]-P;
	if(b)for(i=0,reverse(a+1,a+n),j=P-(P-1)/n;i<n;++i)a[i]=a[i]*1ll*j%P;
}
int main(){
	int m,i;
	scanf("%d%d",&n,&m);
	for(i=0;i<=n;++i)scanf("%d",a+i);
	for(i=0;i<=m;++i)scanf("%d",b+i);
	pre(m+=n),ntt(a),ntt(b);
	for(i=0;i<n;++i)a[i]=a[i]*1ll*b[i]%P;
	ntt(a,1);
	for(i=0;i<=m;++i)printf("%d ",a[i]);
	return 0;
}

评测结果