#3124. 开锁(unlock)

题目描述
A君有 $n$ 个盒子，每个盒子被一把锁锁着，每个盒子内都有一把钥匙。对于每个盒子而言有且仅有一把钥匙能打开锁着它的锁，而打开它后便能拿着放置在这个盒子内的钥匙去开启其他盒子。

现在A君打算随机选择 $k$ 个盒子并用魔法将它们打开，并用所得到的钥匙去尝试开启其他所有的盒子 $f$ 开启一个盒子后，新得到的钥匙还能继续尝试使用）。

A君想知道，最终他能打开所有盒子的概率是多少，请你帮助他。

数据范围
$k le n le 300,T le 100$

题解
考虑到只要每个置换圈被取出其中一个，那就可以打开所有盒子

所以设置换数为 $m$，第 $i$ 个置换中的个数为 $s_i$ ，考虑 $dp$ ，设 $f_{i,j}$ 表示前 $i$ 个，取了 $j$ 个的方案数，则$f_{i,j}=sum_{l=1}^{min(j,s_i)}f_{i-1,j-l} imes C_{s_i}^{l}$

则答案为 $frac{f_{m,k}}{C_{n}^{k}}$

效率： $O(Tnk)$

代码

#include <bits/stdc++.h>
#define db long double
using namespace std;
db c[305][305],ans;
int T,k,a[305],m,b,n,s[305],f[305];
db g[305][305];
int main(){
    c[0][0]=1;
    for (int i=1;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 (scanf("%d",&T);T--;){
        scanf("%d%d",&n,&k);m=0;b=n;
        for (int i=1;i<=n;i++)
            scanf("%d",&a[i]),f[i]=0;
        for (int j,i=1;i<=n;i++)
            if (!f[i]){
                j=a[i];s[f[i]=++m]=1;
                while(!f[j])
                    f[j]=m,j=a[j],s[m]++;
            }
        g[0][0]=1;
        for (int i=1;i<=m;i++)
            for (int j=1;j<=k;j++){
                g[i][j]=0;
                for (int l=1;l<=j && l<=s[i];l++)
                    g[i][j]+=g[i-1][j-l]*c[s[i]][l];
            }
        ans=g[m][k];
        for (int i=1;i<=k;i++) ans/=n,n--,ans*=i;
        printf("%.10LF
",ans);
    }
    return 0;
}