hdu 3625 第一类striling 数

 1 /**
 2 第一类Stirling数是有正负的，其绝对值是包含n个元素的集合分作k个环排列的方法数目。
 3 递推公式为，
 4 S(n,0) = 0, S(1,1) = 1.
 5 S(n+1,k) = S(n,k-1) + nS(n,k)。
 6 
 7 大意： 有n个房间，n把钥匙，钥匙在房间中，问： 在最多破坏k个门的情况下，问有多少种方法，可以将所有的门打开，注意，不能破坏第一个门
 8 
 9 思路： 即是将n个元素分成m个环，得排列方式。。除掉第一个元素独立成环的方式
10 可以得出，这是第一类stirling数。。。
11 **/
12 #include <iostream>
13 #include <cstdio>
14 #include <algorithm>
15 using namespace std;
16 long long s[30][30];
17 long long fac[30];
18 void init(){
19     for(int i=1;i<=20;i++){
20         s[i][0] =0;
21         s[i][i] =1;
22         for(int j=1;j<i;j++){
23             s[i][j] = s[i-1][j-1]+ s[i-1][j] *(i-1);
24         }
25     }
26 
27     fac[0] =1;
28     for(int i=1;i<=20;i++)
29         fac[i] = fac[i-1]*i;
30 }
31 int main()
32 {
33     init();
34     int t;
35     cin>>t;
36     while(t--){
37         int n,k;
38         cin>>n>>k;
39         double ans =0;
40         for(int i=1;i<=k;i++){
41             ans += s[n][i] - s[n-1][i-1];
42         }
43         //cout<<ans<<" "<<fac[n]<<endl;
44         ans = ans/(fac[n]+0.0);
45         printf("%.4lf\n",ans);
46     }
47     return 0;
48 }