【题目描述】
A君有 $n$ 个盒子，每个盒子被一把锁锁着，每个盒子内都有一把钥匙。对于每个盒子而言有且仅有一把钥匙能打开锁着它的锁，而打开它后便能拿着放置在这个盒子内的钥匙去开启其他盒子。
现在A君打算随机选择 $k$ 个盒子并用魔法将它们打开，并用所得到的钥匙去尝试开启其他所有的盒子 $f$ 开启一个盒子后，新得到的钥匙还能继续尝试使用）。
A君想知道，最终他能打开所有盒子的概率是多少，请你帮助他。
【输入格式】
第一行一个整数 $T$ 表示数据组数。
每组数据第一行两个整数 $n,k$，意义见题目描述。
第二行 $n$ 个整数 $a_i$，表示第i个盒子中装有可以打开第 $a_i$ 个盒子的锁的钥匙。
【输出格式】
对于每组数据输出一行表示答案，要求绝对误差不超过4位小数。
【样例】
样例输入
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$ 推了好久没推出来，直接写了个算方案数的，用 $long double$ 存就过了。。。
由于对精度要求不高，所以只用 $long double$ 存前几位有效位的正确性是有保证的。。。
观察题目，不难发现题意就是给你 $n$ 个点构成许多环，求随机选 $k$ 个点覆盖所有环的概率。
考虑 $dp$，设 $f[i][j]$ 表示前 $i$ 个环总共选了 $j$ 个数的方案数，转移时枚举当前环选了几个数，乘上组合数即可。
分析一下效率，第一层循环枚举环和第三层循环枚举选了几个数合在一起是 $O(n)$ 的，因为环的大小总和为 $n$，而第二层循环是 $O(k)$ 的，总复杂度 $O(Tnk)$。
【代码】
#include<bits/stdc++.h>
inline int read ( void )
{
int x=0;char ch;bool f=true;
while ( !isdigit(ch=getchar()) ) if ( ch=='-' ) f=false;
for ( x=ch^48;isdigit(ch=getchar()); ) x=(x<<1)+(x<<3)+(ch^48);
return f ? x : -x ;
}
int n,k,A[310];bool vis[310];
long double C[310][310],f[310][310];
std::vector<int> B;
signed main()
{
for ( int i=0;i<=300;i++ )
{
C[i][0]=1;
for ( int j=1;j<=i;j++ ) C[i][j]=C[i-1][j]+C[i-1][j-1];
}
for ( int T=read();T--; )
{
for ( int i=1;i<=n;i++ ) vis[i]=false;
B.clear();memset(f,0,sizeof(f));
n=read();k=read();
for ( int i=1;i<=n;i++ ) A[i]=read();
for ( int i=1;i<=n;i++ ) if ( !vis[i] )
{
int cnt=1;vis[i]=true;
for ( int x=A[i];x!=i;x=A[x] ) cnt++,vis[x]=true;
B.push_back(cnt);
}
if ( k<(int)B.size() ) { puts("0.000000000");continue; }
std::sort(B.begin(),B.end());
if ( k>=n-B[0]+1 ) { puts("1.000000000");continue; }
f[0][0]=1;
for ( int i=1;i<=(int)B.size();i++ ) for ( int j=i;j<=k;j++ ) for ( int x=1;x<=j-i+1 and x<=B[i-1];x++ ) f[i][j]+=f[i-1][j-x]*C[B[i-1]][x];
printf("%.9LF
",f[(int)B.size()][k]/C[n][k]);
}
}