Steven_Meng's Blog

考虑把门$i$和门$i$中的钥匙指向的门$j$连一条有向边。
打开一扇门，那么这个门处在的环内的所有门都可以被打开，所以图中不可能超过$k$个环。
总共的排列数为$n!$，题目所求的是$n!$个排列中组成$\le k$个环的数量，即第一类斯特林数。
考虑到$1$号门不能炸，用总数$S_u(n,i)$减去$1$号点单独成环的方案$S_u(n-1,i-1)$

答案就是：

$\frac{\sum^k_{i=1}(S_u(n,i)-S_u(n-1,i-1))}{n!}$

代码：

#include <bits/stdc++.h>
#define MAXN 105
using namespace std;
double Su[MAXN][MAXN];
inline void Init(){
    Su[1][0]=0,Su[1][1]=1;
    for (register int i=2;i<MAXN;++i){
        for (register int j=1;j<=i;++j){
            Su[i][j]=Su[i-1][j-1]+(double)(i-1)*Su[i-1][j];
        }
    }
}
int main(){
    Init();
    int t;
    cin>>t;
    while (t--){
        int n,k;
        cin>>n>>k;
        double ans=0;
        for (register int i=1;i<=k;++i){
            ans+=(double)(Su[n][i]-Su[n-1][i-1]);
        }
        double fac=1;
        for (register int i=1;i<=n;++i){
            fac=fac*i;
        }
        printf("%.4lf\n",ans/fac);
    }
}

还是挺短的。