3 3 1 3 2 4 2
0.3333 0.6667 0.6250HintSample Explanation When N = 3, there are 6 possible distributions of keys: Room 1 Room 2 Room 3 Destroy Times #1 Key 1 Key 2 Key 3 Impossible #2 Key 1 Key 3 Key 2 Impossible #3 Key 2 Key 1 Key 3 Two #4 Key 3 Key 2 Key 1 Two #5 Key 2 Key 3 Key 1 One #6 Key 3 Key 1 Key 2 One In the first two distributions, because Key 1 is locked in Room 1 itself and you can’t destroy Room 1, it is impossible to open Room 1. In the third and forth distributions, you have to destroy Room 2 and 3 both. In the last two distributions, you only need to destroy one of Room 2 or Room
有n个房间，n把钥匙，每个房间放置一把钥匙，现在要访问完所有的房间，只允许打破k个房间的门，问有多大的概率可以访问完所有的房间，房间1的门不能被打破。
思路：N个房间形成[1,K]个环时可以。N个元素形成K个环为第一类斯特灵数S[N][K]=S[N-1][K-1]+S[N-1][K]*(N-1)。题目要求不能炸第一个房间，要减去第一个房间独立成环的情况，答案为sigama(S[n][i]-S[n-1][i-1])(1<=i<=K)。
代码：
/* ***********************************************
Author :rabbit
Created Time :2014/4/4 9:02:18
File Name :E.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef __int64 ll;
ll f[30],S[30][30];
int main()
{
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
f[0]=1;for(ll i=1;i<=20;i++)f[i]=f[i-1]*i;
for(ll i=1;i<=20;i++){
S[i][0]=0;S[i][i]=1;
for(ll j=1;j<i;j++)
S[i][j]=(i-1)*S[i-1][j]+S[i-1][j-1];
}
int T;
scanf("%d",&T);
while(T--){
ll n,m;
scanf("%I64d%I64d",&n,&m);
if(n==1||m==0){
puts("0.0000");continue;
}
double ans=0;
for(ll i=1;i<=m;i++)ans+=S[n][i]-S[n-1][i-1];
ans/=f[n];
printf("%.4lf\n",ans);
}
return 0;
}
hdu 3625 第一类斯特灵数,布布扣,bubuko.com
原文：http://blog.csdn.net/xianxingwuguan1/article/details/22912869