HDU3625 Examining the Rooms,第一类斯特林数。
题目链接:HDU3625。
题目
题目描述
有 \(n\) 个房间都被锁上了,开门的钥匙被放在房间里面(每个房间一个),第一个房间的门不能被破坏,求最多破坏 \(k\) 个门,有可能将所有房间都打开的概率。
题解
HDU3625 Examining the Rooms,第一类斯特林数。
关于斯特林数,可以看「OI」斯特林数 Stirling。
思路
考虑要打开 \(i\) 扇门,由于第一个门不能直接打开,所以第一个门一定要与其他门组合在一起,那么根据第一类斯特林数的组合意义,对答案的贡献为 \(\begin{bmatrix}n\\i\end{bmatrix}-\begin{bmatrix}n-1\\i-1\end{bmatrix}\)。
那么答案为
\[\texttt{ans}=\frac{\sum^k _ {i=1}\left(\begin{bmatrix}n\\i\end{bmatrix}-\begin{bmatrix}n-1\\i-1\end{bmatrix}\right)}{n!}\]
预处理 \(n!\) 和第一类斯特林数即可。
代码
#include<cstdio> using namespace std; #define reg register typedef long long ll; #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++) static char buf[100000],*p1=buf,*p2=buf; inline int read(void){ reg char ch=getchar(); reg int res=0; while(ch<'0'||'9'<ch)ch=getchar(); while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar(); return res; } const int MAXN=20+5; ll fac[MAXN],S[MAXN][MAXN]; inline void Init(reg int n){ fac[0]=1; for(reg int i=1;i<=n;++i) fac[i]=fac[i-1]*i; S[0][0]=1; for(reg int i=1;i<=n;++i) for(reg int j=1;j<=i;++j) S[i][j]=S[i-1][j-1]+(i-1)*S[i-1][j]; return; } int n,k; int main(void){ Init(20); reg int T=read(); while(T--){ n=read(),k=read(); reg ll cnt=0; for(reg int i=1;i<=k;++i) cnt+=S[n][i]-S[n-1][i-1]; printf("%.4lf\n",1.0*cnt/fac[n]); } return 0; }
近期评论