BZOJ 5004: 开锁魔法II

题 2、开锁魔法 III
Statement
一日,崔克茜来到小马镇表演魔法。其中一个节目是开锁咒:舞台上有 n
个盒子,每个盒子中有一把钥匙,对于每个盒子而言有且仅有一把钥匙能打开它。
初始时,崔克茜将会随机地选择 k 个盒子用魔法将它们打开。崔克茜想知道最后
所有盒子都被打开的概率,你能帮助她回答这个问题吗?
Input
第一行一个整数 T,表示数据组数(1 ≤ T ≤ 100)。
对于每组数据,第一行有两个整数 n 和
k(1 ≤ n ≤ 300, 0 ≤ k ≤ n)。第二行有 n 个整数 ai,表示第 i
个盒子中装有可以打开第 ai 个盒子的钥匙。
Output
对于每组询问,输出一行表示对应的答案。要求相对误差不超过四位小数。
Sample test(s)
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
output
0.000000000
0.600000000
0.900000000
1.000000000

 

一看就知道是岛娘出的题。。。

因为每个盒子里只放了一把钥匙,而且每个盒子只能被一把钥匙打开。那么我们可以发现题目是给了若干个置换的组合。那么一共有C(n,k)种选择魔法的方式,我们可以通过dp的方式求出总共有多少种全部打开盒子的方案,然后除以C(n,k)即可。dp方程是dp[i][j]表示前i种置换花费j种魔法打开的方案数,那么dp[i][j]=sum(dp[i-1][kk])(j<=k&&0<=kk<j)。注意kk必须要小于j,因为我们一定会在这一组花费一种魔法。

一开始一直想直接概率dp然后发现样例没法过。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注