#P18533. Greek Casino
Greek Casino
Greek Casino
自古以来,人类就喜爱机会游戏。即使以最小公倍数(LCM)闻名的古希腊人也难以抵挡赌博的诱惑。雅典人据此设计了以下系统:参与者购买一张票后,按下面的过程获得一定数量的硬币。
有 个按顺序编号为 的槽。开始时,将一个标记放在槽 ,此时不发放硬币。反复执行:
- 设标记目前所在槽的编号为 。
- 随机产生 到 之间的整数 ,计算 。
- 如果 ,过程立即结束。
- 否则将标记移动到槽 ,参与者获得一枚硬币。
即使 、标记留在原槽,这一步仍会获得一枚硬币。赌场采用给定的概率分布产生随机整数。求整个过程中参与者获得的硬币总数的期望。
输入格式
第一行一个整数 (),表示槽数。
第二行 个整数 ()。每一步产生 的概率为
各步按这个分布独立抽样。输入只有一组数据。
输出格式
输出一行一个实数,表示硬币总数的期望。输出的绝对误差或相对误差至多为 即可。
可以证明,过程以概率 在有限步内终止,而且期望总硬币数有限。
原样例 1
3
1 1 1
3.5000000000
原样例 2
3
1 1 2
3.6666666667