HDU3625 Examining the Rooms

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

答案就是：

\dfrac{\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);
    }
}

还是挺短的。