#P2021094. 收集卡牌
收集卡牌
收集卡牌
题目描述
小林在玩一个抽卡游戏,其中有n种不同的卡牌,编号为1到n。每一次抽卡,她获得第i种卡牌的概率为pi。如果这张卡牌之前已经获得过了,就会转化为一枚硬币。可以用k枚硬币交换一张没有获得过的卡。
小林会一直抽卡,直至集齐了所有种类的卡牌为止,求她的期望抽卡次数。如果你给出的答案与标准答案的绝对误差不超过,则视为正确。
提示:聪明的小林会把硬币攒在手里,等到通过兑换就可以获得剩余所有卡牌时,一次性兑换并停止抽卡。
输入格式
从标准输入读入数据。
输入共两行。第一行包含两个用空格分隔的正整数n,k,第二行给出p1,p2,…,pn,用空格分隔。
输出格式
输出到标准输出。
输出共一行,一个实数,即期望抽卡次数。
数据范围
(原站未提供,导入后需人工补齐)
样例
2 2
0.4 0.6
2.52
4 3
0.006 0.1 0.2 0.694
7.3229920752
提示
样例1解释
共有2种卡牌,不妨记为 A 和 B,获得概率分别为0.4和0.6,2枚硬币可以换一张卡牌。下面给出各种可能出现的情况:
第一次抽卡获得 A,第二次抽卡获得 B,抽卡结束,概率为0.4×0.6=0.24,抽卡次数为2。
第一次抽卡获得 A,第二次抽卡获得 A,第三次抽卡获得 B,抽卡结束,概率为0.4×0.4×0.6=0.096,抽卡次数为3。
第一次抽卡获得 A,第二次抽卡获得 A,第三次抽卡获得 A,用硬币兑换 B,抽卡结束,概率为0.4×0.4×0.4=0.064,抽卡次数为3。
第一次抽卡获得 B,第二次抽卡获得 A,抽卡结束,概率为0.6×0.4=0.24,抽卡次数为2。
第一次抽卡获得 B,第二次抽卡获得 B,第三次抽卡获得 A,抽卡结束,概率为0.6×0.6×0.4=0.144,抽卡次数为3。
第一次抽卡获得 B,第二次抽卡获得 B,第三次抽卡获得 B,用硬币兑换 A,抽卡结束,概率为0.6×0.6×0.6=0.216,抽卡次数为3。
因此答案是0.24×2+0.096×3+0.064×3+0.24×2+0.144×3+0.216×3=2.52。
子任务
对于20%的数据,保证1≤n,k≤5。
对于另外20%的数据,保证所有pi是相等的。
对于100%的数据,保证1≤n≤16,1≤k≤5,所有的pi满足pi≥110000,且∑i=1npi=1。