<题目链接>
<转载于 >>> >
题目大意：
有n个锁着的房间和对应n扇门的n把钥匙，每个房间内有一把钥匙。你可以破坏一扇门，取出其中的钥匙，然后用取出钥匙打开另一扇门（如果取出的钥匙能打开房门则接着打开，取出其中钥匙，如此往复，若打不开则继续破坏一扇门）。最多可以破坏k（k<=n）扇门，但是编号为1的门只能用钥匙打开。求能打开所有门（被破坏或是被钥匙打开）的概率。
解题分析：
钥匙和门的关系是成环状的，打开一个门之后，该环内的所有房间都可以进入，怎么说呢，就拿Hint里的#6来举例，Room1 Room2 Room3是在一个环当中的，假设我破坏了Room3，那么我取出Room3内的钥匙Key2就可以打开Room2，而Room2里有钥匙Key1，那我们又可以打开Room1。
因此，该题就转化成了求N个房间形成1~K个环有多少种可能，然后除以总的分配方案数即为题目要我们求的概率。
首先，总的分配方案数是比较好求的，N的全排列N！种，因为N<=20，有可能超int型范围，所以__int64或long long是必不可少的
其次就是求N个房间成i个环的种类数了，而第一类斯特林数S(N,K)=S(N-1,K-1)+(N-1)*S(N-1,k)恰恰就是求N个元素形成K个非空循环排列的方法数
剩下的就是枚举形成的环，但是要排除掉编号为1的房间独立成环的可能
S(N,M)-S(N-1,M-1)，表示N个元素形成M个环，减去1独自成环，即剩下的N-1个元素形成M-1个环，算得的结果便是所求值
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define eps 1e-7
#define LL long long
using namespace std;
LL fac[] = { };
LL stir1[][]; void INIT()
{
for (int i = ; i<; i++)
fac[i] = fac[i - ] * i; //计算阶乘 for (int i = ; i <= ; i++) //计算stir数组,表示让n个物品形成m个环的方案数
{
stir1[i][] = ;
stir1[i][i] = ;
for (int j = ; j<i; j++)
stir1[i][j] = stir1[i - ][j - ] + (i - )*stir1[i - ][j];
}
} int main()
{
INIT();
int t, n, k;
scanf("%d", &t);
while (t--) {
scanf("%d%d", &n, &k);
if (n == || k == )
{
printf("0.0000\n");
continue;
}
LL sum = ;
for (int i = ; i <= k; i++)
sum += stir1[n][i] - stir1[n - ][i - ]; //减去第一个门独立成环的情况
printf("%.4f\n", (double)sum / fac[n]);
}
return ;
}
2018-08-12