logo AlgoBeat OnlineJudge
登录 注册

#216046. [CSPro 23] 收集卡牌

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

洛谷的测试数据仅供民间交流使用,非官方测试数据。官方评测链接:https://www.cspro.org/


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

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

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

输入格式

从标准输入读入数据。

输入共两行。第一行包含两个用空格分隔的正整数 ,第二行给出 ,用空格分隔。

输出格式

输出到标准输出。

输出共一行,一个实数,即期望抽卡次数。

样例

样例输入 1

2 2
0.4 0.6

样例输出 1

2.52

样例输入 2

4 3
0.006 0.1 0.2 0.694

样例输出 2

7.3229920752

数据范围与提示

样例 1 解释

共有 种卡牌,不妨记为 A 和 B,获得概率分别为 枚硬币可以换一张卡牌。下面给出各种可能出现的情况:

  • 第一次抽卡获得 A,第二次抽卡获得 B,抽卡结束,概率为 ,抽卡次数为
  • 第一次抽卡获得 A,第二次抽卡获得 A,第三次抽卡获得 B,抽卡结束,概率为 ,抽卡次数为
  • 第一次抽卡获得 A,第二次抽卡获得 A,第三次抽卡获得 A,用硬币兑换 B,抽卡结束,概率为 ,抽卡次数为
  • 第一次抽卡获得 B,第二次抽卡获得 A,抽卡结束,概率为 ,抽卡次数为
  • 第一次抽卡获得 B,第二次抽卡获得 B,第三次抽卡获得 A,抽卡结束,概率为 ,抽卡次数为
  • 第一次抽卡获得 B,第二次抽卡获得 B,第三次抽卡获得 B,用硬币兑换 A,抽卡结束,概率为 ,抽卡次数为

因此答案是

子任务

对于 的数据,保证

对于另外 的数据,保证所有 是相等的。

对于 的数据,保证 , ,所有的 满足 ,且