代码

#include<bits/stdc++.h>
using namespace std;
const int N=4e6+5,P=998244353,g=3;
namespace Poly {
	#define LL long long
	LL rev[N],omega[N*2];
	LL qpow(LL a,LL b) {
		LL res=1;
		while(b) {
			if(b&1)res=res*a%P;
			a=a*a%P;
			b>>=1;
		}
		return res;
	}
	void prework() {
		for(int p=2;p<N;p<<=1) {
			omega[p]=1;omega[p+1]=qpow(g,(P-1)/p);
			for(int l=2;l<p/2;++l)
				omega[p+l]=omega[p+l-1]*omega[p+1]%P;
		}
	}
	void NTT(LL *F,int k) {
		int n=1<<k;
		for(int i=0;i<n;++i) {
			rev[i]=(rev[i>>1]>>1)|((i&1)<<(k-1));
			if(rev[i]>i)swap(F[rev[i]],F[i]);
		}
		LL tt;
		for(int p=2,len=1;p<=n;p<<=1,len<<=1)
			for(int i=0;i<n;i+=p)
				for(int l=i;l<i+len;++l) {
					tt=F[l|len]*omega[p+l-i]%P;
					F[l|len]=(F[l]-tt+P)%P;
					F[l]=(F[l]+tt)%P;
				}
	}
	void DFT(LL *F,int k) {NTT(F,k);}
	void IDFT(LL *F,int k) {
		int n=1<<k;
		reverse(F+1,F+n);
		NTT(F,k);
		int inv=qpow(n,P-2);
		for(int i=0;i<n;++i)F[i]=F[i]*inv%P;
	}
	void mul(LL *F,LL *G,int k) {
		int n=1<<k;
		DFT(F,k);
		DFT(G,k);
		for(int i=0;i<n;++i)F[i]=F[i]*G[i]%P;
		IDFT(F,k);
	}
}
LL F[N],G[N];
int n,m;
int main() {
	Poly::prework();
	scanf("%d%d",&n,&m);++n;++m;
	for(int i=0;i<n;++i)scanf("%lld",&F[i]);
	for(int i=0;i<m;++i)scanf("%lld",&G[i]);
	int k=0;
	while((1<<k)<n+m-1)++k;
	Poly::mul(F,G,k);
	for(int i=0;i<n+m-1;++i)printf("%lld ",F[i]);
	return 0;
}

评测结果