题目链接：
?pid=3625
题目大意：
有N个房间，每个房间的要是随机放在某个房间内，概率相同。有K次炸门的机会。
求能打开所有房间门，进入所有房间的概率有多大。
解题思路：
门和钥匙的对应关系出现环。打开一个门后，环内的门都可以打开。也就意味着：
N个房间的钥匙与门形成1~K个环的概率有多大。
也就是求N个元素，构成K个以内的环，且1不成自环的概率。
N个元素形成K个环的方法数是第一类stirling数 S(N，K)。
N个元素形成K个环，且1成自环的方法数是S(N-1，K-1)。
则N个元素形成K个环，且1不成自环的方法数是S(N，K) – S(N-1，，K-1)。
要是随机放的总的方法数为N!。
则概率P(N，K)为( S(N，K) – S(N-1，K-1) + S(N，K-1) – S(N-1，K-2) + … +
S(N，1) – S(N，0) ) / N!
AC代码：
#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#define LL long longusing namespace std;LL F[25],Stirling[25][25];void Solve(){F[0] = 1;for(int i = 1; i <= 20; ++i) //阶乘数组F[i] = i*F[i-1];for(int i = 1; i <= 20; ++i) //算出第一类stirling数Stirling[i][0] = 0;Stirling[1][1] = 1;for(int i = 1; i <= 20; ++i){for(int j = 1; j <= i; ++j){if(i == j)Stirling[i][j] = 1;elseStirling[i][j] = Stirling[i-1][j-1] + (i-1)*Stirling[i-1][j];}}for(int i = 1; i <= 20; ++i) //取绝对值{for(int j = 1; j <= 20; ++j){Stirling[i][j] = abs(Stirling[i][j]);}}}int main(){Solve();int T,N,K;scanf("%d",&T);while(T–){scanf("%d %d",&N,&K);LL sum = 0;for(int i = 1; i <= K; ++i)sum += Stirling[N][i] – Stirling[N-1][i-1];printf("%.4f\n",(double)sum / (double)F[N]); //.4lf输出不了正确结果}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
要铭记在心;每天都是一年中最美好的日子
