代码

#include <algorithm>
#include <cstring>

using namespace std;

/**
 * @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<P?u+v:u+v-P;
					k[i]=u<v?u+P-v:u-v;
				}
		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);
	unsigned *x=new unsigned[s.size()],*y=new unsigned[s.size()];
	memset(x,0,4<<s.m);
	memset(y,0,4<<s.m);
	memcpy(x,a,(n+1)*4);
	memcpy(y,b,(m+1)*4);
	s.solve<1>(x);
	s.solve<1>(y);
	for(unsigned i=0; i<s.size(); ++i) x[i]=1ull*x[i]*y[i]%998244353;
	s.solve<0>(x);
	for(unsigned i=0; i<=n+m; ++i) c[i]=x[i];
	delete[] x;
	delete[] y;
}

评测结果