开锁魔法III
Time Limit: 500 MS Memory Limit: 256000 K
Total Submit: 98(33 users) Total Accepted: 30(23 users) Rating: Special Judge: No
Description
一日，崔克茜来到小马镇表演魔法。
其中有一个节目是开锁咒：舞台上有 n 个盒子，每个盒子中有一把钥匙，对于每个盒子而言有且仅有一把钥匙能打开它。初始时，崔克茜将会随机地选择 k 个盒子用魔法将它们打开。崔克茜想知道最后所有盒子都被打开的概率，你能帮助她回答这个问题吗？
Input
第一行一个整数 T (T <= 100)表示数据组数。
每组数据第一行有两个整数 n 和 k (1 <= n <= 300, 0 <= k <= n)。
第二行有n个整数ai，表示第i个盒子中，装有可以打开第ai个盒子的钥匙。
Output
对于每组数据，输出一行，包含一个实数，代表对应的答案。结果保留四位小数。
Sample Input
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
Sample Output
0.0000
0.6000
0.9000
1.0000
Source

哈尔滨理工大学第五届ACM程序设计竞赛


思路：  

可以形成m个环，以及每个环对应的数量cnt[m]；那么每个环只要选择一个就可以解开所有的箱子

定义dp[i][j]：解决到第i个环，共用了j次魔法的方案数

那么有 dp[i][j] = dp[i-1][j-t]*C(cnt[i],t); 其中t∈[1,j]

其中组合数可以用杨辉三角来求解，三层for循环，dp[m][k]就是可行的方案数。  注意开long double 10^4000次 以及输出用llf

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define bug1 cout <<"bug1"<<endl
#define bug2 cout <<"bug2"<<endl
#define bug3 cout <<"bug3"<<endl
using namespace std;
typedef long long ll;

const int MAX_N=500;
int a[MAX_N];
int vis[MAX_N];
int cnt[MAX_N];
long double dp[400][400];
long double c[400][400];

void init()
{
    c[0][0] = c[1][0] = c[1][1] = 1;
    for (int i=2; i<399; ++i)
    {
        c[i][0] = 1;
        for (int j=1; j<=i; ++j)
            c[i][j] = c[i-1][j] + c[i-1][j-1];
    }
    return ;
}

int main(void){
    init();
    int T;
    cin >> T;
    while(T--){
        memset(dp,0,sizeof(dp));
        memset(vis,0,sizeof(vis));
        int n,k,m=0;
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++)   scanf("%d",&a[i]);
        for(int i=1;i<=n;i++){
            int cnt1=0;
            if(vis[a[i]]==0){
                m++;
                while(vis[a[i]]==0){
                    cnt1++;
                    vis[a[i]]=1;
                    i=a[i];
                }
                cnt[m]=cnt1;
            }
        }
        dp[0][0]=1;
        for(int i=1;i<=m;i++){
            for(int j=i;j<=k;j++){
                for(int t=1;t<=cnt[i];t++){
                    if(t<=j)    dp[i][j]+=dp[i-1][j-t]*c[cnt[i]][t];
                }
            }
        }
        printf("%.4llf\n",dp[m][k]/(1.0*c[n][k]));
    }
}