代码

#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long long
using namespace std;
typedef pair<int,int> PII;
typedef vector<int> poly;
const int Mod=998244353,G=3,Lim=64,winv=932051910;
const LL Mod2=996491788296388609LL;
poly w0={1},W0;
inline int fadd(int x,int y){
	x+=y-2*Mod;
	return x>=0?x:x+2*Mod;
}
inline int fsub(int x,int y){
	x-=y;
	return x>=0?x:x+2*Mod;
}
inline int reduce(LL x){
	uint t=(uint)x*(Mod-2);
	return (x+(LL)t*Mod)>>32;
}
inline int qpow(int x,int y){
	int res=1;
	for(;y;y>>=1,x=(LL)x*x%Mod)
		if(y&1)res=(LL)res*x%Mod;
	return res;
}
template<int tn>
inline void dft(poly &P){
	int m=P.size(),n=m/tn,L=w0.size();
	if(L*2<n)for(w0.resize(n/2);L*2<n;L<<=1){
		int cr=qpow(G,Mod/(L<<2));
		for(int i=0;i<L;++i)w0[i+L]=(LL)cr*w0[i]%Mod;
	}
	if(W0.size()<w0.size()){
		int pr=W0.size(),ed=w0.size();
		W0.resize(ed);
		for(int i=pr;i<ed;++i)W0[i]=reduce((LL)winv*w0[i]);
	}
	for(int k=n,st1,st2;st1=k*tn,st2=st1>>1,k>1;k>>=1)
		for(int i=0,ie=n/k;i<ie;++i)
			for(int p=i*st1,pe=p+st2;p<pe;++p){
				int q=p+st2,z=reduce((LL)P[q]*W0[i]);
				P[q]=fsub(P[p],z),P[p]=fadd(P[p],z);
			}
    for(int &i:P)(i>=Mod)?(i-=Mod):0;
}
template<int tn>
inline void idft(poly &P){
	int m=P.size(),n=m/tn,ni=qpow(n,Mod-2);
	poly rev(n);
	for(int i=1;i<n;++i)rev[i]=rev[i/2]/2+(i&1)*(n/2);
	for(int &i:P)i=1LL*i*ni%Mod;
	for(int i=1;i<n;++i)if(i<rev[i])
		swap_ranges(P.begin()+tn*i,P.begin()+tn*(i+1),P.begin()+tn*rev[i]);
	for(int i=1;i<n/2;++i)
		swap_ranges(P.begin()+tn*i,P.begin()+tn*(i+1),P.begin()+tn*(n-i));
	dft<tn>(P);
	for(int i=1;i<n;++i)if(i<rev[i])
		swap_ranges(P.begin()+tn*i,P.begin()+tn*(i+1),P.begin()+tn*rev[i]);
}
template<int tn>
inline void mul_mod(poly &P,poly &Q){
	int m=P.size(),n=m/tn;
	dft<tn>(P),dft<tn>(Q);
	for(int i=0;i<n;++i){
		vector<uLL>ans(tn<<1);
		for(int j=0;j<tn;++j){
			for(int k=0;k<tn;++k)
				ans[j+k]+=(LL)P[i*tn+j]*Q[i*tn+k];
			if(!((~j)&7))for(int k=j;k<j+tn;++k)
				if(ans[k]>=(Mod2<<3))ans[k]-=Mod2<<3;
		}
		int c=((i&1)?Mod-w0[i>>1]:w0[i>>1]);
		for(int j=0;j<tn;++j)
			P[i*tn+j]=(ans[j]+ans[j+tn]%Mod*c)%Mod;
	}
	idft<tn>(P);
}
template<size_t... m>
inline void solve(index_sequence<m...>,int n,poly &P,poly &Q){
	static void (*ptrs[])(poly&,poly&)={&mul_mod<m+1>...};
	ptrs[n-1](P,Q);
}
inline poly mul(poly P,poly Q){
	int pn=P.size(),qn=Q.size(),rn=pn+qn-1,b=1;
	while((Lim<<b)<rn)++b;
	int tn=((rn-1)>>b)+1,m=tn<<b;
	P.resize(m),Q.resize(m);
	solve(make_index_sequence<Lim>{},tn,P,Q);
	return P.resize(rn),P;
}
void poly_multiply(uint *a,int n,uint *b,int m,uint *c){
	poly P(n+1),Q(m+1);
	for(int i=0;i<=n;++i)P[i]=a[i];
	for(int i=0;i<=m;++i)Q[i]=b[i];
	poly R=mul(P,Q);
	for(int i=0;i<=n+m;++i)c[i]=R[i];
}

评测结果