代码

/**
 * @name FastNumberTheoreticTransform
 * @prefix fntt
*/

template<int P,int G,int K>
struct NTT {
	using ll = unsigned long long;
	unsigned m,mi,r[1 << K],g[1 << K],gi[1 << K];
	inline unsigned size() { return 1<<m; }
	static unsigned qpow(unsigned a,unsigned n) {
		unsigned x=1;
		for(; n; n>>=1,a=(ll)a*a%P) if(n&1) x=(ll)x*a%P;
		return x;
	}
	void getlim(int n) {
		m=0;
		while((1<<m)<=n) ++m;
		for(int i=1; i<(1<<m); ++i) r[i]=(r[i>>1]>>1)|((i&1)<<(m-1));
		mi=qpow(1<<m,P-2);
	}
	template<bool p> void solve(unsigned *a) {
		for(unsigned i=0; i<(1<<m); ++i) if(i<r[i]) swap(a[i],a[r[i]]);
		for(unsigned i=1; i<(1<<m); i<<=1)
			for(unsigned *j=a; j<a+(1<<m); j+=i<<1)
				for(unsigned *k=j,*o=(p?g:gi)+i; k<j+i; ++k,++o) {
					unsigned u=*k,v=(ll)k[i]**o%P;
					*k=u+v;
					if(*k>=P) *k-=P;
					k[i]=u-v;
					if(k[i]<0) k[i]+=P;
				}
		if(!p) for(unsigned i=0; i<(1<<m); ++i) a[i]=(ll)a[i]*mi%P;
	}
	NTT() {
		for(unsigned i=1; i<(1<<K); i<<=1)
			for(unsigned j=i,x=qpow(G,(P-1)/(i<<1)),y=qpow(x,P-2),u=1,v=1; j<i+i; ++j,u=(ll)u*x%P,v=(ll)v*y%P)
				g[j]=u,gi[j]=v;
	}
};

using ntt = NTT<998244353,3,21>;

ntt s;

void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c) {
	s.getlim(n+m+1);
	s.solve<1>(a);
	s.solve<1>(b);
	for(unsigned i=0; i<s.size(); ++i) a[i]=1ull*a[i]*b[i]%998244353;
	s.solve<0>(a);
	for(unsigned i=0; i<=n+m; ++i) c[i]=a[i];
}

评测结果