Steven_MengのBlog

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

答案就是:

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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);
}
}

还是挺短的。

 评论