题解 CF960G 【Bandit Blues】

y2823774827y

2019-04-14 19:44:57

Solution

### 更多姿势$\Longrightarrow$[斯特林数及反演](https://www.cnblogs.com/y2823774827y/p/10700231.html) ## 题目 [CF960G](https://www.luogu.org/problemnew/show/CF960G) ## 做法 设$f(i,j)$为$i$个数的序列,有$j$个前缀最大值的方案数 我们考虑每次添一个最小数,则有:$f(i,j)=f(i-1,j)+(i-1)*f(i-1,j-1)$,显然这是第一类斯特林数 从而我们得到一个朴素的答案: $$Ans=\sum\limits_{i=1}^{n}f_{i,a-1}×f_{n-1-i,b-1}×C_{n-1}^i$$ 理解:枚举$i+1$为最大值添的位置,则已限制了前缀最值个数及后缀最值个数,然后再乘上前半部分所填的数 观察$f_{i,a-1}×f_{n-1-i,b-1}$,发现第一维和唯一: $$Ans=\begin{bmatrix}n-1\\a+b-2\end{bmatrix}C_{a+b-2}^{a-1}$$ 可能会有点难理解:等同于分类成$a+b-2$个环,而环是不考虑顺序的,所以我们选择不考虑打乱顺序地选择环 至此,我们唯一需要的就是快速求出第一类斯特林数$\begin{bmatrix}n-1\\a+b-2\end{bmatrix}$ 即使是单个数也无法有特殊的公式快速得出,所以我们用与求整行第一类斯特林数的方法求出 $O(nlog^2n)$的方法已经烂大街了,分治一下就行 $O(nlogn)$:由于涉及到公式推倒,不是本题解的重点 移步[浅谈斯特林数与斯特林反演](https://www.cnblogs.com/y2823774827y/p/10700231.html),内有详细证明推倒及代码 ## Code ```cpp #include<bits/stdc++.h> typedef int LL; const LL mod=998244353,g=3,_g=332748118,maxn=2e5+9; inline LL Pow(LL base,LL b){ LL ret(1); while(b){ if(b&1) ret=1ll*ret*base%mod; base=1ll*base*base%mod; b>>=1; }return ret; } LL r[maxn],W[maxn]; inline LL Fir(LL n){ LL limit(1),len(0),up(n<<1); while(limit<up){ limit<<=1; ++len; } for(LL i=0;i<limit;++i) r[i]=(r[i>>1]>>1)|((i&1)<<len-1); return limit; } inline void NTT(LL *a,LL n,LL type){ for(LL i=0;i<n;++i) if(i<r[i]) std::swap(a[i],a[r[i]]); for(LL mid=1;mid<n;mid<<=1){ LL wn(Pow(type?g:_g,(mod-1)/(mid<<1))); W[0]=1; for(LL i=1;i<mid;++i) W[i]=1ll*W[i-1]*wn%mod; for(LL R=mid<<1,j=0;j<n;j+=R) for(LL k=0;k<mid;++k){ LL x(a[j+k]),y(1ll*W[k]*a[j+mid+k]%mod); a[j+k]=1ll*(x+y)%mod; a[j+mid+k]=1ll*(x-y+mod)%mod; } } } LL T[maxn],F[maxn],H[maxn],fac[maxn],fav[maxn],tmp[maxn],sum[maxn],B[maxn]; inline LL Mul(LL n,LL *a,LL *b,LL *ans){ LL limit(Fir(n)); NTT(a,limit,1); NTT(b,limit,1); for(LL i=0;i<limit;++i) ans[i]=1ll*a[i]*b[i]%mod; NTT(ans,limit,0); for(LL i=((n-1)<<1)+1;i<limit;++i) a[i]=b[i]=0; return Pow(limit,mod-2); } inline void Solve(LL n,LL *a){ if(!n){ a[0]=1; return; } if(n==1){ a[1]=1; return; } LL len(n/2); Solve(len,a); for(LL i=0;i<=len;++i){ F[i]=1ll*Pow(len,i)*fav[i]%mod; H[i]=1ll*fac[i]*a[i]%mod; } std::reverse(H,H+len+1); LL limit(Fir(len+1)); NTT(F,limit,1); NTT(H,limit,1); for(LL i=0;i<limit;++i) F[i]=1ll*F[i]*H[i]%mod; NTT(F,limit,0); LL ty(Pow(limit,mod-2)); for(LL i=0;i<=len;++i) tmp[i]=1ll*F[len-i]*ty%mod*Pow(fac[i],mod-2)%mod; for(LL i=(len<<1);i<=limit;++i) F[i]=H[i]=0; LL val(Mul(len+1,a,tmp,B)); for(LL i=0;i<=(len<<1);++i) a[i]=1ll*B[i]*val%mod; if(n&1) for(LL i=n;i>=1;--i) a[i]=1ll*(a[i-1]+1ll*(n-1)*a[i]%mod)%mod; } LL n,a,b,m; LL ans[maxn]; int main(){ scanf("%d%d%d",&n,&a,&b); LL val; val=fac[0]=fac[1]=1; for(LL i=2;i<=n;++i) val=fac[i]=1ll*val*i%mod; val=fav[n]=Pow(fac[n],mod-2); for(LL i=n;i>=1;--i) val=fav[i-1]=1ll*val*i%mod; Solve(n-1,ans); n=a+b-2; m=a-1; printf("%d\n",1ll*ans[n]*fac[n]%mod*fav[m]%mod*fav[n-m]%mod%mod); } ```