描述

一日，崔克茜来到小马镇表演魔法。

其中有一个节目是开锁咒：舞台上有 n 个盒子，每个盒子中有一把钥匙，对于每个盒子而言有且仅有一把钥匙能打开它。初始时，崔克茜将会随机地选择 k 个盒子用魔法将它们打开。崔克茜想知道最后所有盒子都被打开的概率，你能帮助她回答这个问题吗？

解题报告:

用时:20min,1A

我们按\(i\)到\(ai\)连边发现，在同一环内的我们选取任意一个即可

所以我们统计这样的连通子图的个数\(m\)，即每一个子图的节点数，所以我们只要保证每一个子图至少选到一个即可，所以我们DP方案数:

\(f[i][j]\)表示前i个子图中选了j个点的方案数

\(f[i][j]+=f[i-1][j-l]*c[s[i]][l]\)

\(s[i]\)表示i这个子图的大小，c为组合数，这里我么要保证每一个至少都选一个那就限制j-l>=i-1即可,最后答案就是\(f[m][k]/c[n][k]\)

#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <cmath>

#define RG register

#define il inline

#define iter iterator

#define Max(a,b) ((a)>(b)?(a):(b))

#define Min(a,b) ((a)<(b)?(a):(b))

using namespace std;

typedef long long ll;

const int N=3e2+5;

int n,k,s[N],m=0,a[N];double f[N][N],c[N][N];bool vis[N];

void prework(){

	for(int i=0;i<N;i++){

		c[i][0]=1;

		for(int j=1;j<=i;j++)

			c[i][j]=c[i-1][j-1]+c[i-1][j];

	}

}

void work()

{

	m=0;

	scanf("%d%d",&n,&k);

	for(int i=1;i<=n;i++)scanf("%d",&a[i]),vis[i]=false;

	int x,t=0;

	for(int i=1;i<=n;i++){

		if(vis[i])continue;

		x=i;t=0;

		while(!vis[x]){

			vis[x]=true;

			x=a[x];t++;

		}

		s[++m]=t;

	}

	memset(f,0,sizeof(f));

	f[0][0]=1;

	for(int i=1;i<=m;i++){

		for(int j=1;j<=k;j++)

			for(int l=1;l<=s[i] && j-l>=i-1;l++){

				f[i][j]+=f[i-1][j-l]*c[s[i]][l];

			}

	}

	double ans=(double)f[m][k]/(c[n][k]*1.0);

	printf("%.4lf\n",ans);

}

int main()

{

	int T;cin>>T;

	prework();

	while(T--)work();

	return 0;

}