Submission #70662075

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=4e6+15,P=998244353,G=3;
inline ll ksm(ll a,int b){
	ll res=1;
	while(b){
		if(b&1)res=res*a%P;
		a=a*a%P,b>>=1;
	}
	return res;
}
inline int gt(int x){int tp=1;while(tp<=x)tp<<=1;return tp;}
ll pw[N];
ll sinv[N];
ll fac[N],inv[N];
inline void init(int n){
	int W1=1,W2=0;
	while((W1<<1)<=n)W1<<=1;
	ll ts=ksm(G,(P-1)/(W2=W1<<1));pw[W1]=1;
	for(int i=W1+1;i<W2;i++)pw[i]=pw[i-1]*ts%P;
	for(int i=W1-1;i>=1;i--)pw[i]=pw[i<<1];
	sinv[1]=1;
	for(int i=2;i<=W2;i++)sinv[i]=sinv[P%i]*(P-P/i)%P;
	fac[0]=inv[0]=1;
	for(int i=1;i<=W2;i++)fac[i]=fac[i-1]*i%P;
	inv[W2]=ksm(fac[W2],P-2);
	for(int i=W2-1;i>=1;i--)inv[i]=inv[i+1]*(i+1)%P;
}
int rev[N];
inline void crv(int lim,int len){for(int i=1;i<lim;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(len-1));}
using vi=vector<int>; 
inline int mol(int x,int y){return x+y>=P?x+y-P:x+y;}
struct Poly{
	vi f;
	Poly(){}
	Poly(int len){f.resize(len);}
	inline void resize(int len){f.resize(len);}
	inline int& operator [](const int x){return f[x];}
	inline const int& operator [](const int x)const{return f[x];}
	void NTT(int lim,int typ){
		crv(lim,__lg(lim));
		if(typ==-1)reverse(f.begin()+1,f.end());
		if((int)f.size()!=lim)f.resize(lim);
		for(int i=0;i<lim;i++)if(i<rev[i])swap(f[i],f[rev[i]]);
		for(int mid=1;mid<lim;mid<<=1){
			for(int j=0;j<lim;j+=(mid<<1)){
				for(int k=0;k<mid;k++){
					int x=f[j+k],y=pw[mid+k]*f[j+k+mid]%P;
					f[j+k]=mol(x,y),f[j+k+mid]=mol(x,P-y);
				}
			}
		}
		if(typ==-1){
			for(int i=0;i<lim;i++)f[i]=f[i]*sinv[lim]%P;
		}
	}
	void Mul(Poly &B,int lim){
		Poly X=*this,Y=B;
		X.NTT(lim,1);Y.NTT(lim,1);
		for(int i=0;i<lim;i++)X[i]=1ll*X[i]*Y[i]%P;
		X.NTT(lim,-1);*this=X;
	}
	void Inv(int n){
		Poly X(1),t1,t2;X[0]=f[0]==1?1:ksm(f[0],P-2);
		for(int len=2;(len>>1)<=n;len<<=1){
			int las=len>>1;t1=X;
			for(int i=0;i<las;i++)t1[i]=mol(t1[i],t1[i]);
			int lim=len<<1;X.NTT(lim,1); 
			for(int i=0;i<lim;i++)X[i]=1ll*X[i]*X[i]%P;
			t2.resize(len);
			for(int i=0;i<len;i++)t2[i]=(i<=n?f[i]:0);
			t2.NTT(lim,1);
			for(int i=0;i<lim;i++)X[i]=1ll*X[i]*t2[i]%P;
			X.NTT(lim,-1);X.resize(len);
			for(int i=0;i<len;i++)X[i]=P-X[i],(X[i]==P)&&(X[i]==0);
			for(int i=0;i<las;i++)X[i]=mol(t1[i],X[i]);
		}
		X.resize(n+1);
		*this=X;
	}
	void Sqrt(int n){
		Poly X(1),t1,t2;X[0]=1;
		for(int len=2;(len>>1)<=n;len<<=1){
			int las=len>>1;
			t1=X;X.resize(len);X.Inv(len-1);t2.resize(len);
			for(int i=0;i<len;i++)t2[i]=(i<=n?f[i]:0);
			X.Mul(t2,len<<1);X.resize(len);
			for(int i=0;i<las;i++)X[i]=mol(t1[i],X[i]);
			for(int i=0;i<len;i++)X[i]=sinv[2]*X[i]%P;
		}
		X.resize(n+1);*this=X;
	}
	void Intg(){
		int len=f.size();
		resize(len+1);
		for(int i=len;i>=1;i--)f[i]=f[i-1]*sinv[i]%P;
		f[0]=0;
	}
	void Diff(){
		int len=f.size();
		for(int i=0;i<len-1;i++)f[i]=1ll*(i+1)*f[i+1]%P;
		resize(len-1);
	}
	void Ln(int n){
		resize(n+1);
		Poly B=*this;B.Inv(n);
		Diff();Mul(B,gt(n<<1));
		resize(n);Intg();
	}
	void Exp(int n){
		Poly X(1),t1;X[0]=1;
		for(int len=2;(len>>1)<=n;len<<=1){
			t1=X;X.Ln(len-1);
			for(int i=0;i<len;i++)X[i]=mol(P-X[i],i<=n?f[i]:0);
			X[0]=mol(X[0],1);
			X.Mul(t1,len<<1);X.resize(len);
		}
		X.resize(n+1);*this=X;
	}
	void Kpow(int n,int k){
		Ln(n);for(int i=0;i<=n;i++)f[i]=1ll*f[i]*k%P;
		Exp(n);
	}
};
int n,m;
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	init(gt(max(n,m)+1));
	Poly F(n+1);
	F[0]=1;
	for(int i=1;i<=m;i++){
		Poly G(n+1);
		for(int j=0;j<=min(n,i);j++){
			G[j]=inv[j];
		}
		F.Mul(G,gt((n+1)<<1));
		F.resize(n+1);
	}
	cout<<F[n]*fac[n]%P<<"\n";
	return 0;
}

Submission Info

Judge Result