#P2021094. 收集卡牌

收集卡牌

收集卡牌

题目描述

小林在玩一个抽卡游戏,其中有n种不同的卡牌,编号为1到n。每一次抽卡,她获得第i种卡牌的概率为pi。如果这张卡牌之前已经获得过了,就会转化为一枚硬币。可以用k枚硬币交换一张没有获得过的卡。

小林会一直抽卡,直至集齐了所有种类的卡牌为止,求她的期望抽卡次数。如果你给出的答案与标准答案的绝对误差不超过10−410^{−4},则视为正确。

提示:聪明的小林会把硬币攒在手里,等到通过兑换就可以获得剩余所有卡牌时,一次性兑换并停止抽卡。

输入格式

从标准输入读入数据。

输入共两行。第一行包含两个用空格分隔的正整数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。