描述
一日，崔克茜来到小马镇表演魔法。
其中有一个节目是开锁咒：舞台上有 n 个盒子，每个盒子中有一把钥匙，对于每个盒子而言有且仅有一把钥匙能打开它。初始时，崔克茜将会随机地选择 k 个盒子用魔法将它们打开。崔克茜想知道最后所有盒子都被打开的概率，你能帮助她回答这个问题吗？
输入
第一行一个整数 T (T ≤ 100)表示数据组数。 对于每组数据，第一行有两个整数 n 和 k (1 ≤ n ≤ 300, 0 ≤ k ≤ n)。 第二行有 n 个整数 ai，表示第 i 个盒子中，装有可以打开第 ai 个盒子的钥匙。
输出
对于每组询问，输出一行表示对应的答案。要求相对误差不超过四位小数。
样例输入
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 [i][j]
那么前一个状态为 dp [i-1][j-use],即用j-use把钥匙打开前i-1个阶段的盒子一共有的方法数
也就是说打开第i个阶段的盒子用了use个钥匙，一共有 C(cnt,use)种方法，cnt为第i个阶段一共有cnt个待打开的盒子
那么根据乘法原理
dp[i][j]=dp[i-1][j-use]*C(cnt,use) ，
但是前一个状态不唯一，也就是use的值可以变化，所以要方法累加 即dp[i][j]+=dp[i-1][j-use]*C(cnt,use). 这里dp[i][j]是未知的，要求它就必须知道dp[i-1][j-use]，也就是用已知的状态去推出未知的状态。
代码
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <iomanip>
using namespace std;
int n,k;
int match[];
double c[][];
bool vis[];
double dp[][];
vector<int>loop;
void getComb()
{
for(int i=;i<=;i++)
{
c[i][]=c[i][i]=1.0;
for(int j=;j<i;j++)
c[i][j]=c[i-][j]+c[i-][j-];
}
} int main()
{
getComb();
int t;
cin>>t;
while(t--)
{
cin>>n>>k;
for(int i=;i<=n;i++)
cin>>match[i];
loop.clear();
memset(vis,,sizeof(vis));
for(int i=;i<=n;i++)//求循环节
{
if(vis[i]) continue;
int cnt=,cur=i;
while(!vis[cur])
{
cnt++;
vis[cur]=;
cur=match[cur];
}
loop.push_back(cnt);
} int num=loop.size();
if(k<num)
{
printf("%.9lf\n",0.0);
continue;
} memset(dp,,sizeof(dp));
dp[][]=1.0;
for(int i=;i<num;i++)
{
for(int j=;j<k;j++)
{
if(dp[i][j]==) continue;
for(int use=;use<=loop[i]&&j+use<=k;use++)
dp[i+][j+use]+=dp[i][j]*c[loop[i]][use];
}
}
printf("%.9lf\n",dp[num][k]/c[n][k]);
}
return ;
} 查看代码
点击查看代码