代码

#include<bits/stdc++.h>
#define M 2100005
const int P=998244353,G=3,invG=332748118;
using namespace std;
int a[M],b[M],c[M],n,m;
namespace NTT{
	int A[M],B[M],r[M],w[M];
	int pow(int a,int x){
		int res=1;
		while(x){
			if(x&1)res=1ll*res*a%P;
			a=1ll*a*a%P;
			x>>=1;
		}
		return res;
	}
	void DFT(int *x,int n,int p){
		for(int i=0;i<n;i++)if(i<r[i])swap(x[i],x[r[i]]);
		w[0]=1;
		for(int i=1;i<n;i<<=1){
			int wn=pow(p>0?G:invG,(P-1)/i>>1);
			for(int j=i-2;j>=0;j-=2)w[j+1]=1ll*wn*(w[j]=w[j>>1])%P;
			for(int j=0;j<n;j+=(i<<1)){
				for(int k=0;k<i;k++){
					int t=1ll*x[i+j+k]*w[k]%P;
					x[i+j+k]=(x[j+k]-t+P)%P;
					x[j+k]=(x[j+k]+t)%P;
				}
			}
		}
	}
	void mult(const int *a,const int *b,int x,int y,int *c){
		int n=1;
		while(n<=x+y)n<<=1;
		memcpy(A,a,4*x+4),memcpy(B,b,4*y+4);
		memset(A+x+1,0,4*(n-x)),memset(B+y+1,0,4*(n-y));
		for(int i=0;i<n;i++)r[i]=(r[i>>1]>>1)|((i&1)*(n>>1));
		DFT(A,n,1),DFT(B,n,1);
		for(int i=0;i<n;i++)A[i]=1ll*A[i]*B[i]%P;
		DFT(A,n,-1);
		int inv=pow(n,P-2);
		for(int i=0;i<n;i++)c[i]=1ll*A[i]*inv%P;
	}
};
using NTT::mult;
int main() {
	scanf("%d%d",&n,&m);
	for(int i=0;i<=n;i++)scanf("%d",&a[i]);
	for(int i=0;i<=m;i++)scanf("%d",&b[i]);
	mult(a,b,n,m,c);
	for(int i=0;i<=n+m;i++)printf("%d ",c[i]);
	puts("");
	return 0;
}

评测结果