HDU 3625（斯特林数）

题意：

有n个房间，每一个房间里面都有一把钥匙（可能是该门的钥匙，也可能是别的门的钥匙），开始的时候，所有房间都是锁着的，你有k次炸开某个房间门的机会，但是由于1号房间住着一个很重要的人，所以你不能炸开1号房间，只能是用钥匙开。（你炸开了一个房间，就可以那里面的钥匙去开别的门），输入n，k。问能把所有门都打开的概率是多少？

题解：

我们发现，钥匙和房间能组成一个环，如果其中一扇门被炸开，那么该环上所有的门都可以用钥匙开。

房间号	钥匙
房间号	钥匙
1	2
2	3
3	4
4	1

如果把2号门炸开，就可以拿钥匙开3号门，拿4号钥匙开1号门..........

如果所有房间能组成（小于或等于k）个环，并且1号钥匙不在一号门，那么就是可行的

计算概率时的分母为n！(因为1号钥匙所在位置有n种情况，2号有(n-1)种,所以一共有n!）

P = \(\frac{\sum_{i = 1}^{k}(S(n, i) - S(n-1,i-1))}{n!}\)

n个房间能形成（1~k）个环 - 2~n号房间形成（0~k-1）个环

#include 
    
     long long s[30][30], f[30];//默认初始化为0int main() {    s[0][0]  = f[0] = 1;    for(int i = 1; i < 25; i++) {        f[i] = f[i-1] * i;        for(int j = 1; j <= i; j++) {            s[i][j] = s[i-1][j-1] + s[i-1][j] * (i - 1);        }    }    int t;    scanf("%d", &t);    while(t--) {        int n, k;        long long sum = 0;        scanf("%d %d", &n, &k);        for(int i = 1; i <= k; i++) sum += s[n][i] - s[n-1][i-1];        printf("%.4f\n", (double)sum / f[n]);    }    return 0;}