P16029 [CSPro 23] 收集卡牌

洛谷的测试数据仅供民间交流使用，非官方测试数据。官方评测链接：。

小林在玩一个抽卡游戏，其中有 $n$ 种不同的卡牌，编号为 $1$ 到 $n$。每一次抽卡，她获得第 $i$ 种卡牌的概率为 $p_i$。如果这张卡牌之前已经获得过了，就会转化为一枚硬币。可以用 $k$ 枚硬币交换一张没有获得过的卡。 小林会一直抽卡，直至集齐了所有种类的卡牌为止，求她的期望抽卡次数。如果你给出的答案与标准答案的绝对误差不超过 $10^{-4}$，则视为正确。 提示：聪明的小林会把硬币攒在手里，等到通过兑换就可以获得剩余所有卡牌时，一次性兑换并停止抽卡。

从标准输入读入数据。 输入共两行。第一行包含两个用空格分隔的正整数 $n, k$，第二行给出 $p_1, p_2, \dots, p_n$，用空格分隔。

输出到标准输出。 输出共一行，一个实数，即期望抽卡次数。

### 样例 1 解释 共有 $2$ 种卡牌，不妨记为 A 和 B，获得概率分别为 $0.4$ 和 $0.6$，$2$ 枚硬币可以换一张卡牌。下面给出各种可能出现的情况： - 第一次抽卡获得 A，第二次抽卡获得 B，抽卡结束，概率为 $0.4 \times 0.6 = 0.24$，抽卡次数为 $2$。 - 第一次抽卡获得 A，第二次抽卡获得 A，第三次抽卡获得 B，抽卡结束，概率为 $0.4 \times 0.4 \times 0.6 = 0.096$，抽卡次数为 $3$。 - 第一次抽卡获得 A，第二次抽卡获得 A，第三次抽卡获得 A，用硬币兑换 B，抽卡结束，概率为 $0.4 \times 0.4 \times 0.4 = 0.064$，抽卡次数为 $3$。 - 第一次抽卡获得 B，第二次抽卡获得 A，抽卡结束，概率为 $0.6 \times 0.4 = 0.24$，抽卡次数为 $2$。 - 第一次抽卡获得 B，第二次抽卡获得 B，第三次抽卡获得 A，抽卡结束，概率为 $0.6 \times 0.6 \times 0.4 = 0.144$，抽卡次数为 $3$。 - 第一次抽卡获得 B，第二次抽卡获得 B，第三次抽卡获得 B，用硬币兑换 A，抽卡结束，概率为 $0.6 \times 0.6 \times 0.6 = 0.216$，抽卡次数为 $3$。 因此答案是 $0.24 \times 2 + 0.096 \times 3 + 0.064 \times 3 + 0.24 \times 2 + 0.144 \times 3 + 0.216 \times 3 = 2.52$。 ### 子任务 对于 $20\%$ 的数据，保证 $1 \leq n, k \leq 5$。 对于另外 $20\%$ 的数据，保证所有 $p_i$ 是相等的。 对于 $100\%$ 的数据，保证 $1 \leq n \leq 16$, $1 \leq k \leq 5$，所有的 $p_i$ 满足 $p_i \geq \frac{1}{10000}$，且 $\sum_{i=1}^{n} p_i = 1$。