#P18533. Greek Casino

Greek Casino

Greek Casino

自古以来,人类就喜爱机会游戏。即使以最小公倍数(LCM)闻名的古希腊人也难以抵挡赌博的诱惑。雅典人据此设计了以下系统:参与者购买一张票后,按下面的过程获得一定数量的硬币。

有 N≥3N\ge3 个按顺序编号为 1,2,…,N1,2,\ldots,N 的槽。开始时,将一个标记放在槽 11,此时不发放硬币。反复执行:

  1. 设标记目前所在槽的编号为 xx。
  2. 随机产生 11 到 NN 之间的整数 yy,计算 z=lcm⁡(x,y)z=\operatorname{lcm}(x,y)。
  3. 如果 z>Nz>N,过程立即结束。
  4. 否则将标记移动到槽 zz,参与者获得一枚硬币。

即使 z=xz=x、标记留在原槽,这一步仍会获得一枚硬币。赌场采用给定的概率分布产生随机整数。求整个过程中参与者获得的硬币总数的期望。

输入格式

第一行一个整数 NN(3≤N≤1053\le N\le10^5),表示槽数。

第二行 NN 个整数 W1,W2,…,WNW_1,W_2,\ldots,W_N(1≤Wi≤10001\le W_i\le1000)。每一步产生 ii 的概率为

Wi∑j=1NWj.\frac{W_i}{\sum_{j=1}^N W_j}.

各步按这个分布独立抽样。输入只有一组数据。

输出格式

输出一行一个实数,表示硬币总数的期望。输出的绝对误差或相对误差至多为 10−910^{-9} 即可。

可以证明,过程以概率 11 在有限步内终止,而且期望总硬币数有限。

原样例 1

3
1 1 1
3.5000000000

原样例 2

3
1 1 2
3.6666666667