题目大意：给出n个房间，打开房间门的办法有撞击和用钥匙打开，编号1的门不能撞击。已知每个房间里有n间房间中某间房子的钥匙，问在k次撞击之内，求把房间门全部打开的概率。
解题思路：1）第一扇门必须撞开。
2）当钥匙无法打开关闭的门的时候，必须继续采取撞开的方式
3）编号1的门不能撞击。
3）到这里，题目演变成了求在n间房间中形成少于k个环的概率（编号1的门不能独立成环）。
.................然后，我就不会做了。接着上网百度了一下就n个元素划分成k个环的方法~~，.....第一次接触了所谓的第一类斯特林数。
斯特林数学习资料：
http://www.mathchina.com/usr1PvjRWKew/5/2/CBB9CCD8C1D6CAFD_1178220836.bmp 或者：
/Files/wyh123/CBB9CCD8C1D6CAFD_1178220877.doc 继续思路：
4）在这里我们很容易得出n把钥匙的排列数是n！，只要我们求出所有可能的方案数，则概率p=sum/n!
5）形成少于k个环的总数有s(n,k)+s(n,k-1)+.......+s(n,1)
6）由于编号1的房间不能独立成环，所以要计算出编号1房间独立成环的成功方案数：s(n-1,k-1)+s(n-1,k-2)+.....s(n-1,2)+s(n-1,1)
7）总方案就为：sum=s(n,k)+s(n,k-1)+.....+s(n,1)-(s(n-1,k-1)+s(n-1,k-2)+.....s(n-1,2)+s(n-1,1))
到这里问题解决。发现自己的数学基础还是不行啊，仍需加油，补充！！！
1
#include <iostream>
2#include <cstring>
3#include <cstdlib>
4#include <cmath>
5#include <cstdio>
6#include <algorithm>
7
8using namespace std;
9
10long long f[30];
11long long s[30][30];
12int i,k,n,T;
13double sum;
14
15void init()
16
{
17
int i,j;
18 f[1]=1;
19 for(i=2;i<30;i++)
20 f[i]=i*f[i-1];
21 for(i=0;i<30;i++)
22 s[i][0]=0;
23 s[1][1]=1;
24 for(i=2;i<30;i++)
25
{
26 for(j=1;j<=i;j++)
27 s[i][j]=s[i-1][j-1]+(i-1)*s[i-1][j];
28
}
29
}
30
31
32int main()
33{ scanf("%d",&T);
34 init();
35 while(T--)
36 {
37 scanf("%d%d",&n,&k);
38 sum=0;
39 for(i=1;i<=k;i++)
40 sum=sum+s[n][i]-s[n-1][i-1];
41 sum=1.0*sum/f[n];
42 printf("%.4lf\n",sum);
43 }
44 return 0;
45}
46