hihocoder1075【开锁魔法】

题意是给你一个 \(1～n\) 的置换，求选 \(k\) 个可以遍历所有点的概率。

题目可以换个模型：有 \(n\) 个球，有 \(cnt\) 种不同的颜色，求选出 \(k\) 个球包含所有颜色的概率。

根据概率的定义，我们只需求出合法的方案数即可。

设 \(f[i][j]\) 表示选 \(j\) 个球，包含前 \(i\) 种颜色的方案数。转移枚举第 \(i\) 种颜色选的个数即可。

根据乘法原理和加法原理可得：

初始条件是 \(f[0][0]=1\)，结果是 \(f[cnt][k]/c[n][k]\)。

#include <bits/stdc++.h>

using namespace std;

#define db double

#define ll long long

#define RG register

inline int gi()

{

	RG int ret; RG bool flag; RG char ch;

	ret=0, flag=true, ch=getchar();

	while (ch < '0' || ch > '9')

		ch == '-' ? flag=false : 0, ch=getchar();

	while (ch >= '0' && ch <= '9')

		ret=(ret<<3)+(ret<<1)+ch-'0', ch=getchar();

	return flag ? ret : -ret;

}

const db pi = acos(-1.0);

const int N = 305, inf = 1<<30;

db c[N][N],f[N][N];

int to[N],a[N];

bool vis[N];

int main()

{

	freopen("magic.in","r",stdin);

	freopen("magic.out","w",stdout);

	int T,n,m,i,j,p,cnt;

	for (i=1; i<N; ++i)

		{

			c[i][0]=c[i][i]=1;

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

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

		}

	T=gi();

	while (T--)

		{

			n=gi(), m=gi(), cnt=0;

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

				{

					vis[i]=false, a[i]=0;

					for (j=0; j<=m; ++j)

						f[i][j]=0;

				}

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

				to[i]=gi();

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

				{

					if (vis[i])

						continue;

					p=i, cnt++;

					while (!vis[p])

						a[cnt]++, vis[p]=true, p=to[p];

				}

			if (m < cnt)

				{

					puts("0.00000000000");

					continue;

				}

			f[0][0]=1;

			for (i=0; i<=cnt; ++i)

				for (j=0; j<m; ++j)

					{

						if (f[i][j] == 0)

							continue;

						for (p=1; p<=a[i+1] && p+j <= m; ++p)

							f[i+1][j+p]+=f[i][j]*c[a[i+1]][p];

					}

			printf("%.9f\n",f[cnt][m]/c[n][m]);

		}

	return 0;

}