代码

#define N 280005
#define p 998244353
#define G 332748118
int lim;
int r[N];

inline int POW(int a,int b=p-2,int ans=1){
	for(;b;b>>=1,a=1ll*a*a%p)
		if(b&1) ans=1ll*ans*a%p;
	return ans;
}
void NTT(int *f,int pd){
	for(int i=0;i<lim;i++)
		if(i<r[i]) swap(f[i],f[r[i]]);
	for(int w,len=1;len<lim;len<<=1){
		w=POW(pd,(p-1)/(len<<1));
		for(int b=1,k=0;k<lim;k+=(len<<1),b=1)
			for(int i=k;i<k+len;i++,b=1ll*b*w%p){
				int now=1ll*b*f[i+len]%p;
				f[i+len]=(f[i]-now+p)%p,f[i]=(f[i]+now)%p;
			}
	}
}


void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c)
{
	for(lim=1;lim<=n+m;lim<<=1);
	for(int i=1;i<lim;i++)
		r[i]=(r[i>>1]>>1)|((i&1)?lim>>1:0);
	NTT(a,3);NTT(b,3);
	for(int i=0;i<lim;i++)
		c[i]=1ll*a[i]*b[i]%p;
	NTT(c,G); int inv=POW(lim);
	for(int i=0;i<=n+m;i++)
                c[i]=1ll*c[i]*inv%p;
}

评测结果