题解 P5434 【【模板】有标号荒漠计数】
Great_Influence
2019-06-16 19:39:45
仙人掌计数后再套一个 $exp$ 就完事了。
仙人掌计数可以参考[这篇](https://www.luogu.org/blog/user7035/loj-161-xian-ren-zhang-ji-shuo)。
代码:
```cpp
#include<bits/stdc++.h>
#define Rep(i,a,b) for(register int i=(a);i<=(b);++i)
#define Repe(i,a,b) for(register int i=(a);i>=(b);--i)
#define rep(i,a,b) for(register int i=(a);i<(b);++i)
#define pb push_back
#define mx(a,b) (a>b?a:b)
#define mn(a,b) (a<b?a:b)
typedef unsigned long long uint64;
typedef unsigned int uint32;
typedef long long ll;
using namespace std;
namespace IO
{
const uint32 Buffsize=1<<15,Output=1<<24;
static char Ch[Buffsize],*S=Ch,*T=Ch;
inline char getc()
{
return((S==T)&&(T=(S=Ch)+fread(Ch,1,Buffsize,stdin),S==T)?0:*S++);
}
static char Out[Output],*nowps=Out;
inline void flush(){fwrite(Out,1,nowps-Out,stdout);nowps=Out;}
template<typename T>inline void read(T&x)
{
x=0;static char ch;T f=1;
for(ch=getc();!isdigit(ch);ch=getc())if(ch=='-')f=-1;
for(;isdigit(ch);ch=getc())x=x*10+(ch^48);
x*=f;
}
template<typename T>inline void write(T x,char ch='\n')
{
if(!x)*nowps++='0';
if(x<0)*nowps++='-',x=-x;
static uint32 sta[111],tp;
for(tp=0;x;x/=10)sta[++tp]=x%10;
for(;tp;*nowps++=sta[tp--]^48);
*nowps++=ch;
}
}
using namespace IO;
void file()
{
FILE*DSD=freopen("a.in","r",stdin);
FILE*CSC=freopen("a.out","w",stdout);
}
const int MAXN=1<<21;
namespace poly
{
const int mod=998244353,gen=3;
static int g[23][MAXN],iv[MAXN];
inline int power(int u,int v)
{
register int sm=1;
for(;v;v>>=1,u=(uint64)u*u%mod)if(v&1)
sm=(uint64)sm*u%mod;
return sm;
}
inline void predone()
{
Rep(i,1,21)
{
g[i][0]=1,g[i][1]=power(gen,(mod-1)>>i);
Rep(j,2,4e5)g[i][j]=(ll)g[i][j-1]*g[i][1]%mod;
}
iv[1]=1;
Rep(i,2,4e5)iv[i]=mod-(uint64)mod/i*iv[mod%i]%mod;
}
static int Len,rev[MAXN];
inline void calrev()
{
int II=log(Len)/log(2)-1;
Rep(i,1,Len-1)rev[i]=rev[i>>1]>>1|(i&1)<<II;
}
inline int ad(int u,int v){return(u+=v)>=mod?u-mod:u;}
inline void NTT(int*F,int typ)
{
Rep(i,1,Len-1)if(i<rev[i])swap(*(F+i),*(F+*(rev+i)));
for(register int i=2,ii=1,t=1;i<=Len;i<<=1,ii<<=1,++t)
{
for(register int j=0;j<Len;j+=i)
{
rep(k,0,ii)
{
register int tt=(uint64)*(F+j+k+ii)*g[t][k]%mod;
*(F+j+k+ii)=ad(*(F+j+k),mod-tt);
*(F+j+k)=ad(*(F+j+k),tt);
}
}
}
if(typ==-1)
{
reverse(F+1,F+Len);
register uint64 invn=power(Len,mod-2);
rep(i,0,Len)*(F+i)=invn**(F+i)%mod;
}
}
static int X[MAXN],Y[MAXN],Iv[MAXN];
inline void mul(int *a,int *b,int *c,int lenl,int lenr)
{
if((ll)lenl*lenr<=300)
{
memset(X,0,sizeof(int)*(lenl+lenr+1));
Rep(i,0,lenl)Rep(j,0,lenr)
X[i+j]=(X[i+j]+(ll)a[i]*b[j])%mod;
Rep(i,0,lenl+lenr)c[i]=X[i];
return;
}
for(Len=2;Len<=lenl+lenr;Len<<=1);
calrev();
memcpy(X,a,sizeof(int)*(lenl+1));
memcpy(Y,b,sizeof(int)*(lenr+1));
rep(i,lenl+1,Len)X[i]=0;
rep(i,lenr+1,Len)Y[i]=0;
NTT(X,1),NTT(Y,1);
rep(i,0,Len)X[i]=(ll)X[i]*Y[i]%mod;
NTT(X,-1);
memcpy(c,X,sizeof(int)*(lenl+lenr+1));
rep(i,lenl+lenr+1,Len)c[i]=0;
}
inline void Inv(int*F,int*G,int ln)
{
Iv[0]=power(F[0],mod-2);
for(register int Ln=2;Ln>>1<=ln;Ln<<=1)
{
rep(i,0,min(Ln,ln+1))X[i]=F[i];
rep(i,0,Ln)Y[i]=0;
rep(i,0,(Ln>>1))Y[i]=Iv[i];
Len=Ln,calrev();
NTT(X,1),NTT(Y,1);
rep(i,0,Ln)X[i]=(uint64)X[i]*Y[i]%mod;
NTT(X,-1);
rep(i,0,(Ln>>1))X[i]=0;
NTT(X,1);
rep(i,0,Ln)X[i]=(uint64)X[i]*Y[i]%mod;
NTT(X,-1);
rep(i,(Ln>>1),Ln)Iv[i]=mod-X[i];
}
memcpy(G,Iv,sizeof(int)*(ln+1));
}
static int ExX[MAXN],ExY[MAXN],Op[MAXN];
inline void Deriv(int*F,int*G,int ln)
{Rep(i,1,ln)G[i-1]=(uint64)F[i]*i%mod;G[ln]=0;}
inline void Inter(int*F,int*G,int ln)
{Repe(i,ln,1)G[i]=(uint64)F[i-1]*iv[i]%mod;G[0]=0;}
static int LnX[MAXN];
inline void Ln(int*F,int*G,int ln)
{
Deriv(F,LnX,ln),Inv(F,G,ln);
for(Len=2;Len<=ln<<1;Len<<=1);
rep(i,ln+1,Len)LnX[i]=G[i]=0;
calrev();
NTT(LnX,1),NTT(G,1);
rep(i,0,Len)G[i]=(uint64)G[i]*LnX[i]%mod;
NTT(G,-1);
Inter(G,G,ln);
}
inline void Exp(int *F,int *H,int *G,int ln)
{
int Lx=ln+1,Hf=(Lx>>1)-1;
Op[Hf]=0;
memcpy(Op,H,sizeof(int)*Hf);
rep(i,0,Hf)Op[Hf]=(Op[Hf]+(ll)F[i+1]
*(i+1)%mod*H[Hf-1-i]%mod)%mod;
Op[Hf]=(ll)Op[Hf]*iv[Hf]%mod;
memset(Op+(Lx>>1),0,sizeof(int)*Lx/2);
Ln(Op,ExX,Lx);
rep(i,0,Lx>>1)ExX[i]=ad(F[i+(Lx>>1)],mod-ExX[i+(Lx>>1)]);
memcpy(ExY,Op,sizeof(int)*Lx/2);
memset(ExX+(Lx>>1),0,sizeof(int)*Lx/2);
memset(ExY+(Lx>>1),0,sizeof(int)*Lx/2);
Len=Lx;
calrev();
NTT(ExY,1),NTT(ExX,1);
rep(i,0,Len)ExX[i]=(ll)ExX[i]*ExY[i]%mod;
NTT(ExX,-1);
memcpy(Op+Len/2,ExX,sizeof(int)*Lx/2);
memcpy(G,Op,sizeof(int)*ln);
}
void cdq_Exp(int*a,int*F,int l,int r)
{
if(l==r)
{
if(!l)F[l]=1;
else F[l]=(ll)F[l]*iv[l]%mod;
return;
}
int md=(l+r)>>1;cdq_Exp(a,F,l,md);
for(Len=2;Len<=r-l;Len<<=1);
calrev();
memset(X,0,sizeof(int)*Len);
memset(Y,0,sizeof(int)*Len);
memcpy(X,F+l,sizeof(int)*(md-l+1));
memcpy(Y,a,sizeof(int)*(r-l));
NTT(X,1),NTT(Y,1);
rep(i,0,Len)X[i]=(ll)X[i]*Y[i]%mod;
NTT(X,-1);
Rep(i,md+1,r)F[i]=ad(F[i],X[i-l-1]);
cdq_Exp(a,F,md+1,r);
}
inline void EXP(int *F,int *G,int ln)
{
Rep(i,1,ln)Op[i-1]=(ll)F[i]*i%mod,Op[i]=0;
memset(G,0,sizeof(int)*(ln+1));
cdq_Exp(Op,G,0,ln);
}
}
using poly::mul;
using poly::power;
using poly::Len;
using poly::calrev;
using poly::NTT;
using poly::mod;
using poly::predone;
using poly::Inv;
using poly::Inter;
using poly::Deriv;
using poly::Ln;
using poly::Exp;
using poly::ad;
using poly::EXP;
static int F[MAXN],X[MAXN];
static int G[MAXN],H[MAXN];
void getans(int*F,int lim)
{
F[1]=1;
static int hf;
for(register int len=4;len>>1<lim;len<<=1)
{
hf=len>>1;
rep(i,hf,len)H[i]=G[i]=0;
G[0]=0;
rep(i,1,hf)H[i]=mod-F[i],G[i]=ad(H[i],H[i]);
G[0]=H[0]=2;
Inv(G,G,len-1);
Len=len,calrev();
rep(i,0,len)X[i]=F[i];
NTT(H,1),NTT(X,1);
rep(i,0,len)H[i]=(ll)H[i]*X[i]%mod;
NTT(H,-1);
mul(H,G,H,len-2,len-1);
rep(i,len,len<<1)H[i]=0;
Exp(H,F+1,H,len-1);
Repe(i,len-1,1)H[i]=H[i-1];H[0]=0;
rep(i,0,hf)G[i]=F[i];
rep(i,hf,len)G[i]=0;
G[0]=mod-1;
Len=len,calrev();
NTT(G,1);
rep(i,0,len)G[i]=(ll)G[i]*G[i]%mod;
NTT(G,-1);
Inv(G,G,hf-1);
++G[0];
rep(i,hf,len)G[i]=0;
mul(G,H,G,hf-1,hf);
G[0]=ad(G[0],mod-2);
rep(i,hf,len)G[i]=0;
Inv(G,G,hf-1);
rep(i,0,len)H[i]=2ll*(H[i]+mod-F[i])%mod;
Len=len,calrev();
NTT(H,1),NTT(G,1);
rep(i,0,len)H[i]=(ll)H[i]*G[i]%mod;
NTT(H,-1);
rep(i,hf,len)F[i]=mod-H[i];
}
}
static int fac[MAXN],inv[MAXN];
static int a[MAXN];
inline void Chkmax(int&u,int v){u<v?u=v:0;}
int main()
{
file();
predone();
static int _,n=0;
read(n);
getans(F,n);
fac[0]=1,inv[1]=1;
Rep(i,2,n)inv[i]=mod-(ll)mod/i*inv[mod%i]%mod;
Rep(i,1,n)fac[i]=(ll)fac[i-1]*i%mod;
Rep(i,1,n)F[i]=(ll)F[i]*inv[i]%mod;
EXP(F,F,n);
write((ll)F[n]*fac[n]%mod);
flush();
return 0;
}
```