代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 4000005
#define int unsigned long long
const int MOD=998244353;

namespace iobuff{
	const int LEN=1000000;
	char in[LEN+5], out[LEN+5];
	char *pin=in, *pout=out, *ed=in, *eout=out+LEN;
	inline char gc(void)
	{
		return pin==ed&&(ed=(pin=in)+fread(in, 1, LEN, stdin), ed==in)?EOF:*pin++;
	}
	inline void pc(char c)
	{
		pout==eout&&(fwrite(out, 1, LEN, stdout), pout=out);
		(*pout++)=c;
	}
	inline void flush()
	{ fwrite(out, 1, pout-out, stdout), pout=out; }
	template<typename T> inline void scan(T &x)
	{
		static int f;
		static char c;
		c=gc(), f=1, x=0;
		while(c<'0'||c>'9') f=(c=='-'?-1:1), c=gc();
		while(c>='0'&&c<='9') x=10*x+c-'0', c=gc();
		x*=f;
	}
	template<typename T> inline void putint(T x, char div)
	{
		static char s[100];
		static int top;
		top=0;
		x<0?pc('-'), x=-x:0;
		while(x) s[top++]=x%10, x/=10;
		!top?pc('0'), 0:0;
		while(top--) pc(s[top]+'0');
		pc(div);
	}
}
using namespace iobuff;

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];
	inline int glim(int n)
	{
		int l=0;
		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));
		for(int i=1; i<(1<<l); i<<=1)
		{
			wn[i]=1;
			int mw=qpow(g, (MOD-1)/(i<<1));
			for(int j=1; j<i; ++j) wn[i+j]=1ll*wn[i+j-1]*mw%MOD;
		}
	}
	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;
			for(int i=0; i<n; i+=len) for(int j=i; j<i+c; ++j)
			{
				int x=f[j], y=1ll*f[j+c]*wn[c+j-i]%MOD;
				f[j]=x+y, f[j+c]=MOD+x-y;
			}
		}
		for(int i=0; i<n; ++i) f[i]%=MOD;
		if(mod)
		{
			std::reverse(f+1, f+n);
			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));
	}
}
signed main()
{
	scan(n), scan(m);
	for(int i=0; i<=n; ++i) scan(a[i]);
	for(int i=0; i<=m; ++i) scan(b[i]);
	NTT::mul(a, b, c, n, m);
	for(int i=0; i<=n+m; ++i) putint(c[i], ' ');
	flush();
	return 0;
}

评测结果