代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MOD 998244353
#define N 8000005
//const int MOD=998244353;
int n, m, a[N], b[N], c[N];
inline int mval(int x) { return x>=MOD?x-MOD:x; }
inline void inc(int &x, int a) { x=mval(x+a); }
inline void dec(int &x, int a) { x=mval(MOD+x-a); }
inline int qpow(int x, int p)
{ int ret=1; while(p) { if(p&1) ret=1ll*ret*x%MOD; p>>=1, x=1ll*x*x%MOD; } return ret; }
inline int inv(int x) { return qpow(x, MOD-2); }
namespace NTT{
	const int g=3;
	int A[N], B[N], C[N], rev[N], wn[N], iwn[N];
	inline int glim(int n)
	{
		int l=1;
		while(n) n>>=1, ++l;
		return l;
	}
	inline void init(int l)
	{
		for(int i=1; i<(1<<l); ++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
	}
	inline void ntt(int *f, int n, int mod)
	{
		for(int i=0; i<n; ++i) if(i<rev[i]) std::swap(f[i], f[rev[i]]);
		for(int len=2; len<=n; len<<=1)
		{
			int c=len>>1;
			int wn=qpow(g, (MOD-1)/len);
			if(mod) wn=inv(wn);
			for(int i=0; i<n; i+=len) for(int j=i, w=1; j<i+c; ++j, w=1ll*w*wn%MOD)
			{
				int x=f[j], y=1ll*f[j+c]*w%MOD;
				f[j]=mval(x+y), f[j+c]=mval(MOD+x-y);
			}
		}
		if(mod)
		{
			int iv=inv(n);
			for(int i=0; i<n; ++i) f[i]=1ll*f[i]*iv%MOD;
		}
	}
	inline void mul(int *a, int *b, int *c, int n, int m)
	{
		int l=glim(n+m);
		init(l);
		memcpy(A, a, sizeof(int)*(n+1));
		memcpy(B, b, sizeof(int)*(m+1));
		std::fill(A+n+1, A+(1<<l)+1, 0);
		std::fill(B+m+1, B+(1<<l)+1, 0);
		ntt(A, (1<<l), 0), ntt(B, (1<<l), 0);
		for(int i=0; i<(1<<l); ++i) C[i]=1ll*A[i]*B[i]%MOD;
		ntt(C, (1<<l), 1);
		memcpy(c, C, sizeof(int)*(n+m+1));
	}
}
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);
	NTT::mul(a, b, c, n, m);
	for(int i=0; i<=n+m; ++i) printf("%d ", c[i]);
	return 0;
}

评测结果