描述
一日,崔克茜来到小马镇表演魔法。
其中有一个节目是开锁咒:舞台上有 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
1,每个盒子都有一个入度和一个出度,以之前二分图拆点的经验来看,必然会形成很多个环。
2,每个环至少选择一个盒子。
3,每个环至少选择一个盒子的组合数,联想到母函数,组合数。
4.*YY。可以DP,但是误差可能大一些。可以全部求出来再除,这样误差小一些。
(ps:学会了母函数再搞组合是要多一分灵感!弯的four)
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;
const int maxn=;
double c[maxn][maxn];
double a[maxn],b[maxn];
int loop[maxn],num[maxn],cnt,laxt[maxn],n;
void init()
{
cnt=;
for(int i=;i<=n;i++){
a[i]=b[i]=num[i]=loop[i]=laxt[i]=;
}
}
void getc()
{
int i,j;
for(i=;i<=;i++){
c[i][]=c[i][i]=1.0;
for(j=;j<i;j++) c[i][j]=c[i-][j]+c[i-][j-];
}
return ;
}
void geta()
{
int i,j,k;
for(i=;i<=num[];i++) a[i]=c[num[]][i],b[i]=0.0;
for(i=;i<=cnt;i++){
for(j=;j<=n;j++)
for(k=;k<=num[i];k++)
if(j+k<=n) b[j+k]+=a[j]*c[num[i]][k];//不是+1
for(j=;j<=n;j++){
a[j]=b[j];
b[j]=;
}
}
}
int main()
{
int i,j,T,k;
scanf("%d",&T);
getc();//组合数C
while(T--){
scanf("%d%d",&n,&k);
init();
for(i=;i<=n;i++) scanf("%d",&laxt[i]);
for(i=;i<=n;i++){//分组
if(!loop[i]){
++cnt;
for(j=i;;j=laxt[j]){
if(loop[j]) break;
loop[j]=cnt;
num[cnt]++;
}
}
}
geta();//保证每个环至少一个的母函数
printf("%.9lf\n",a[k]/c[n][k]);
}
return ;
}