生活随笔
收集整理的这篇文章主要介绍了
hdu-3625 Examining the Rooms（斯特灵数第一类）
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
http://acm.hdu.edu.cn/showproblem.php?pid=3625
/*****************************************************************************************************************************
** 题意： 有n个房间，每个房间都有一把钥匙可以打开其他房间的门；
** 你想检查所有的房间，但初始所有的门都是被锁着的，
** 你可以破坏一些门，检查它，并取出门里的钥匙去打开其他房间（1号门不允许破坏）
** 问你最多可以破坏K个门，能够检查所有的房间的概率
** 题解：斯特灵数（Stirling）第一类。
** 如果不考虑那个VIP，N个房间可以被最多K把钥匙打开的情况，
** 实际上就是1..N的置换组成最多K个环的情况，这个就是第一类strling数之和stirling[n][1] stirling[n][2] ... stirling[n][k]。
** 在这些情况里面，如果钥匙1恰好锁在房间1里也是不行的，所以还要减去N-1个房间被最多K-1把钥匙打开的情况数。
*******************************************************************************************************************************/
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
LL stirling[25][25];
LL fac[25];
void init(){for(int i = 1;i <= 20;i++){stirling[i][i] = 1;for(int j = 1;j < i;j++)stirling[i][j] = stirling[i-1][j-1] + stirling[i-1][j] * (i-1);}fac[1] = 1;for(int i = 2;i <= 20;i++)fac[i] = i * fac[i-1] ;
}
int main(){init();int t,n,K;cin >> t;while(t--){cin >> n >> K;LL sum = 0;for(int i = 1;i <= K;i++){sum += stirling[n][i] - stirling[n-1][i-1];}printf("%.4lf\n",1.0*sum / fac[n]);}return 0;
}
总结
以上是生活随笔为你收集整理的hdu-3625 Examining the Rooms（斯特灵数第一类）的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
