代码

#include <stdio.h>
#include <algorithm>
#define N 2100000
#define cIz 998244353
typedef long long ll;

inline int Add(int a,int b,int m) {
	return (a+=b)<m?a:a-m;
}
inline int Sub(int a,int b,int m) {
	return (a-=b)<0?a+m:a;
}
inline int Mul(int a,int b,int m) {
	return (ll)a*b%m;
}
inline int Pow(int a,int b,int m) {
	int ans=1;
	for(;b;b>>=1) {
		if(b&1) ans=Mul(ans,a,m);
		a=Mul(a,a,m);
	}
	return ans;
}
inline int Inv(int a,int m) {
	return Pow(a,m-2,m);
}
inline int Div(int a,int b,int m) {
	return (ll)a*Inv(b,m)%m;
}

int L,rev[N],w[N];
void init() {
	register int i;
	rev[0]=0;
	for(i=1;i<1<<L;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(L-1));
}
template<int mod,int g>
void NTT(int *f,bool b) {
	register int i,j,k;
	register int e,w,t;
	for(i=0;i<1<<L;++i) if(i<rev[i]) std::swap(f[i],f[rev[i]]);
	for(i=0;i<L;++i) {
		e=Pow(g,mod-1>>i+1,mod);
		if(b) e=Inv(e,mod);
		for(j=0;j<1<<L;j+=2<<i) {
			w=1;
			for(k=0;k<1<<i;++k) {
				t=Mul(w,f[j|k|1<<i],mod);
				f[j|k|1<<i]=Sub(f[j|k],t,mod);
				f[j|k]=Add(f[j|k],t,mod);
				w=Mul(w,e,mod);
			}
		}
	}
	if(b) {
		t=Inv(1<<L,mod);
		for(i=0;i<1<<L;++i) f[i]=Mul(f[i],t,mod);
	}
}

int main() {
	static int f[N],g[N];
	register int i,n,m;
	scanf("%d%d",&n,&m);
	for(i=0;i<=n;++i) scanf("%d",f+i);
	for(i=0;i<=m;++i) scanf("%d",g+i);
	for(L=0;1<<L<n+m+1;++L);
	init();
	NTT<cIz,3>(f,0);
	NTT<cIz,3>(g,0);
	for(i=0;i<1<<L;++i) f[i]=Mul(f[i],g[i],cIz);
	NTT<cIz,3>(f,1);
	for(i=0;i<=n+m;++i) printf("%d ",f[i]);
	return 0;
}

评测结果