代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#define int unsigned long long
#define N 4000005
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); }
	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;
		}
	}
	void poly_multiply(unsigned *a, signed n, unsigned *b, int m, unsigned *c)
	{
		int l=glim(n+m);
		init(l);
		for(int i=0; i<=n; ++i) A[i]=a[i];
		for(int i=0; i<=m; ++i) B[i]=b[i];
		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);
		for(int i=0; i<=n+m; ++i) c[i]=C[i];
	}

评测结果