代码

#include<bits/stdc++.h>
using namespace std;
const int N=(1<<22)+20;
const int mod=998244353;
typedef vector<int> vec;
typedef unsigned long long ull;


namespace Math{
	inline int add(int x,int y){return (x+y>=mod)?x+y-mod:x+y;}
	inline int dec(int x,int y){return (x-y<0)?x-y+mod:x-y;}
	inline void inc(int &x,int y){x=add(x,y);}
	inline void rec(int &x,int y){x=dec(x,y);}
	inline int ksm(int x,int y){
		int ret=1;
		for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) ret=1ll*ret*x%mod;
		return ret; 
	}
	int iv[N],tp;
	inline void init_inv(int n){
		if(!tp){iv[0]=iv[1]=1;tp=2;}
		for(;tp<=n;++tp) iv[tp]=1ll*(mod-mod/tp)*iv[mod%tp]%mod;
	}
}
using namespace Math;

int Wn[N<<1],lg[N],r[N],tot;
inline void init_poly(int n){
	int p=1;while(p<=n)p<<=1;
	for(int i=2;i<=p;++i) lg[i]=lg[i>>1]+1;
	for(int i=1;i<p;i<<=1){
		int wn=ksm(3,(mod-1)/(i<<1));
		Wn[++tot]=1;
		for(int j=1;j<i;++j) ++tot,Wn[tot]=1ll*Wn[tot-1]*wn%mod;
	}
}
inline void init_pos(int lim){
	int len=lg[lim]-1;
	for(int i=0;i<lim;++i) r[i]=(r[i>>1]>>1)|((i&1)<<len);
}

ull fr[N];
const ull Mod=998244353;
inline void NTT(int *f,int lim,int tp){
	for(int i=0;i<lim;++i) fr[i]=f[r[i]];
	for(int mid=1;mid<lim;mid<<=1){
		for(int len=mid<<1,l=0;l+len-1<lim;l+=len){
			for(int k=l;k<l+mid;++k){
				ull w1=fr[k],w2=fr[k+mid]*Wn[mid+k-l]%Mod;
				fr[k]=w1+w2;fr[k+mid]=w1+Mod-w2; 
			}
		}
	}
	for(int i=0;i<lim;++i) f[i]=fr[i]%Mod;
	if(!tp){
		reverse(f+1,f+lim);
		int iv=ksm(lim,mod-2);
		for(int i=0;i<lim;++i) f[i]=1ll*f[i]*iv%mod;
	}
}
int f[N],g[N];
void poly_multiply(unsigned *a,int n,unsigned *b,int m,unsigned *c){
	n++;m++;init_poly(n+m);
	int rec=n+m-1;
	int len=lg[rec],lim=1<<len+1;
	init_pos(lim);
	for(int i=0;i<n;++i) f[i]=a[i];
	for(int i=0;i<m;++i) g[i]=b[i];
	NTT(f,lim,1);NTT(g,lim,1);
	for(int i=0;i<lim;++i) f[i]=1ll*f[i]*g[i]%mod;
	NTT(f,lim,0);
	for(int i=0;i<rec;++i) c[i]=f[i];
}

评测结果