生活随笔
收集整理的這篇文章主要介紹了
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（斯特灵数第一类）的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
