题面:www.lydsy.com/JudgeOnline/upload/task.pdf

第一种方法比较好理解，这道题这么做的话也非常简单.
这里讲一下第二种方法:
易得箱子之间都是环的关系，令 $f[i][j]$ 表示一共开了 $j$ 个箱子并成功打开前 $i$ 个环的概率. 
则 $f[i][j+p]+=\frac{f[i-1][j]\times C^{j}_{sum[i-1]}\times C^{p}_{c_{i}}} {C_{sum[i]}^{j+p}}$        
我们强制给第 $i$ 个环分配 $p$ 个箱子，那么产生这种情况的概率是 $\frac{C^{j}_{sum[i-1]}\times C^{p}_{c_{i}}} {C_{sum[i]}^{j+p}}$，而还需满足前 $i-1$ 个箱子也被打开，那么这个概率就是 $f[i-1][j]$，这两个相乘就是发生当前局面的概率. 

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <cstring>

#define setIO(s) freopen(s".in","r",stdin)

#define N 307

using namespace std;

double fac[N],f[N][N];

bool vis[N];

int cir[N],sum[N],a[N];

inline void calc()

{

    int n,k,i,j,tot=0,p;

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

    memset(vis,0,sizeof(vis));

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

    for(i=1;i<=n;++i) scanf("%d",&a[i]), fac[i]=fac[i-1]+log(i);

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

    {

        if(vis[i]) continue;

        cir[++tot]=0;

        for(j=i;!vis[j];j=a[j]) vis[j]=1,cir[tot]++;

    }

    sum[0]=0,f[0][0]=1.0000;

    for(i=1;i<=tot;++i) sum[i]=sum[i-1]+cir[i];

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

        for(j=i-1;j<k&&j<=sum[i-1];++j)

            for(p=1;p<=cir[i]&&j+p<=k;++p)

            {

                double tmp=exp(fac[sum[i-1]]+fac[cir[i]]+fac[j+p]+fac[sum[i]-j-p]-fac[j]-fac[sum[i-1]-j]-fac[p]-fac[cir[i]-p]-fac[sum[i]]);

                f[i][j+p]+=f[i-1][j]*tmp;

            }

    printf("%.9f\n",f[tot][k]);

}

int main()

{

    // setIO("input");

    int T,i,j;

    scanf("%d",&T);

    for(i=1;i<=T;++i) calc();

    return 0;

}