时间限制:6000ms
单点时限:1000ms
内存限制:256MB
描述
一日，崔克茜来到小马镇表演魔法。
其中有一个节目是开锁咒：舞台上有 n 个盒子，每个盒子中有一把钥匙，对于每个盒子而言有且仅有一把钥匙能打开它。初始时，崔克茜将会随机地选择 k 个盒子用魔法将它们打开。崔克茜想知道最后所有盒子都被打开的概率，你能帮助她回答这个问题吗？
输入
第一行一个整数 T (T ≤ 100)表示数据组数。 对于每组数据，第一行有两个整数 n 和 k (1 ≤ n ≤ 300, 0 ≤ k ≤ n)。 第二行有 n 个整数 ai，表示第 i 个盒子中，装有可以打开第 ai 个盒子的钥匙。
输出
对于每组询问，输出一行表示对应的答案。要求相对误差不超过四位小数。
- 样例输入
-
4
5 1
2 5 4 3 1
5 2
2 5 4 3 1
5 3
2 5 4 3 1
5 4
2 5 4 3 1 - 样例输出
-
0.000000000
0.600000000
0.900000000
1.000000000 题解：
这个题目十分巧妙，首先，我们想利用题目中已经告诉我们们的一个性质，对于每个盒子而言有且仅有一把钥匙能打开它，所以，如果我们把一个盒子看成一个点，那么你打开一个盒子，就可以前往盒子里下标的那个点，那么又因为图上的那个性质，相当于保证了每个点的如果只能为一，且出度也为一，所以整个图就会由若干环环组成。
知道这个，我们想把每个点都跑到，那么显然每个环都至少存在一个点就可以了。那么考虑ｄｐ出所有可行的方案数，dp[i][j]表示处理到ｉ这个环，用了ｊ次选点机会的方案数，那么dp[i][j]=dp[i][j-use]*c(size[i],use)。其中use表示你用于ｉ这个环上选的点数，size[i]表示ｉ这个环的点数。dp[0][0]=1.
最后用dp[num][k]除以总方案数就可以了。 代码：#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#define MAXN 320
using namespace std;
double c[MAXN][MAXN];
int size[MAXN],b[MAXN],g[MAXN];
double dp[MAXN][MAXN];
int n,k; void pre(){
c[][]=;
for(int i=;i<=;i++)
for(int j=;j<=;j++){
if(!j) c[i][j]=;
else c[i][j]=c[i-][j-]+c[i-][j];
}
} int main()
{
int t;cin>>t;
pre();
while(t--){
scanf("%d%d",&n,&k);
memset(g,,sizeof(g));
for(int i=;i<=n;i++) scanf("%d",&g[i]);
int num=;
memset(b,,sizeof(b));
memset(size,,sizeof(size));
for(int i=;i<=n;i++){
if(b[i]) continue;
num++;int now=i;
while(!b[now]){
b[now]=;
size[num]++;
now=g[now];
}
}
if(k<num){
printf("%0.9f\n",);
continue;
}
memset(dp,,sizeof(dp));
dp[][]=;
for(int i=;i<num;i++)
for(int j=;j<k;j++){
if(!dp[i][j]) continue;
for(int use=;use<=size[i+]&&j+use<=k;use++){
dp[i+][j+use]+=dp[i][j]*c[size[i+]][use];
}
}
printf("%0.9f\n",dp[num][k]/c[n][k]);
}
return ;
}