hdu 3625 第一类striling 数

/**
第一类Stirling数是有正负的，其绝对值是包含n个元素的集合分作k个环排列的方法数目。
递推公式为，
S(n,0) = 0, S(1,1) = 1.
S(n+1,k) = S(n,k-1) + nS(n,k)。

大意： 有n个房间，n把钥匙，钥匙在房间中，问： 在最多破坏k个门的情况下，问有多少种方法，可以将所有的门打开，注意，不能破坏第一个门

思路： 即是将n个元素分成m个环，得排列方式。。除掉第一个元素独立成环的方式
可以得出，这是第一类stirling数。。。
**/
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
long long s[30][30];
long long fac[30];
void init(){
    for(int i=1;i<=20;i++){
        s[i][0] =0;
        s[i][i] =1;
        for(int j=1;j<i;j++){
            s[i][j] = s[i-1][j-1]+ s[i-1][j] *(i-1);
        }
    }

    fac[0] =1;
    for(int i=1;i<=20;i++)
        fac[i] = fac[i-1]*i;
}
int main()
{
    init();
    int t;
    cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        double ans =0;
        for(int i=1;i<=k;i++){
            ans += s[n][i] - s[n-1][i-1];
        }
        //cout<<ans<<" "<<fac[n]<<endl;
        ans = ans/(fac[n]+0.0);
        printf("%.4lf
",ans);
    }
    return 0;
}