题目
有\(n\)个房间，\(n\)个钥匙，每个钥匙随机出现在一个房间里，一个房间里有且仅有一个钥匙。我们现在手上没有钥匙，但我们要搜索所有的房间，所以我们有\(k\)次机会把一个房间炸开。一号房间里住着一个重要的人，所以一号房间不能炸。给出\(n\)，\(k\)，求我们能够成功搜索所有房间的概率。
分析
英文题看了一会儿……
我们发现，对于一个由房间和钥匙组成的环，我们只需要随便炸开其中一个房间即可搜索这个环上所有的房间。所以成功的情况就是环的个数小于等于\(k\)并且一号钥匙不在一号房里。
我自己推出的公式比较复杂，基本思路就是，首先求出不管１号房间的可能情况，再减去\(\frac{1}{n}\)，即减去一号钥匙在一号房间里的情况，再加上一号钥匙在一号房间且不可行的情况，一起除以\(n!\)即可：
\[\begin{aligned}
ans=\frac{\sum _{i=1}^k s(n,i)}{n!}-\frac{1}{n}+\frac{\sum _{i=k+1}^n s(n-1,i-1)}{n!}
\end{aligned}
\]
ans=\frac{\sum _{i=1}^k s(n,i)}{n!}-\frac{1}{n}+\frac{\sum _{i=k+1}^n s(n-1,i-1)}{n!}
\end{aligned}
\]
然而hjh告诉我有更简洁的方法：
\[\begin{aligned}
ans=\frac{\sum _{i=1}^k s(n,i)-s(n-1,i-1)}{n!}
\end{aligned}
\]
ans=\frac{\sum _{i=1}^k s(n,i)-s(n-1,i-1)}{n!}
\end{aligned}
\]
成功的情况数就是\(n\)个房间中的环小于等于\(k\)个的情况数减去后\(n-1\)个房间刚好组成\(k-1\)个环（即1号房间自己组成一个环）的情况数。
其实这两个式子在数学上应该是等价的，但这种在枚举的时候计算的思想很棒。
代码
hdu上g++ WA了，c++可以AC。
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
using namespace std;
int read() {
int x=0,f=1;
char c=getchar();
for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
for (;isdigit(c);c=getchar()) x=x*10+c-'0';
return x*f;
}
const int maxn=1<<5;
long long s[maxn][maxn];
long double jc[maxn],ans;
int main() {
#ifndef ONLINE_JUDGE
freopen("test.in","r",stdin);
#endif
s[0][0]=jc[0]=1;
for (int i=1;i<maxn;++i) {
jc[i]=jc[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=read();
while (T--) {
int n=read(),k=read();
long double tmp=0;
for (int i=1;i<=k;++i) tmp+=s[n][i]-s[n-1][i-1];
ans=(tmp/jc[n]);
/*
ans-=1.0/n;
tmp=0;
for (int i=k;i<n;++i) tmp+=s[n-1][i];
ans+=(tmp/jc[n]);
*/
printf("%.4Lf\n",ans);
}
}