UOJ Logo Universal Online Judge

UOJ

#706. 【UER #10】随机薅羊毛

附件下载 统计

码圣 skip 蚤为了庆祝自己得奖,举办了一场抽奖活动,并提供了丰厚的礼品。

skip 蚤设立了 $n$ 个抽奖机,第 $i$ 个抽奖机每次抽奖成功的概率为 $p_i$。

胖胖蚤喜欢薅羊毛!于是他决定不断抽奖,直到中奖为止。

胖胖蚤很笨,不知道怎样抽奖,于是他决定采用这样的策略:

  1. 初始他等概率随机选择一台机器抽奖。
  2. 如果上一次抽奖失败了,他将等概率随机选择一台和当前机器不同的抽奖机(即 $n-1$ 台)继续抽奖,并重复第二步。

胖胖蚤想让聪明的你算算,他期望需要抽几次奖才能成功。

输入格式

第一行一个整数 $n$,表示抽奖机台数。

接下来一行 $n$ 个整数,第 $i$ 个整数 $a_i$ 表示 $p_i=\frac{a_i}{10^6}$。

输出格式

一行一个小数,表示期望需要抽奖次数。如果你的输出与答案绝对或相对误差不超过 $10^{-9}$ 则认为正确。

样例一

input

2
500000 250000

output

2.6

explanation

两台抽奖机的概率分别为 $\frac{1}{2},\frac{1}{4}$。

因为只有两台抽奖机,胖胖蚤一定交替抽奖。

如果先抽第一台,则期望为:$\frac{1}{2}\times 1+\frac{1}{2}\times\frac{1}{4}\times 2+\frac{1}{2}\times\frac{3}{4}\times\frac{1}{2}\times 3+\cdots=\frac{12}{5}$。

如果先抽第二台,则期望为:$\frac{1}{4}\times 1+\frac{3}{4}\times\frac{1}{2}\times 2+\frac{3}{4}\times\frac{1}{2}\times\frac{1}{4}\times 3+\cdots=\frac{14}{5}$。

答案为两者平均数,即为 $\frac{13}{5}=2.6$。

样例二

见附件下载的 ex_game2.inex_game2.ans

数据范围与提示

子任务编号 $n\leq$ 分值
$1$ $2$ $10$
$2$ $300$ $30$
$3$ $3000$ $30$
$4$ $10^6$ $30$

对于所有数据,保证 $2\leq n\leq 10^6,1\leq a_i\lt 10^6$。

时间限制:$\texttt{2s}$

空间限制:$\texttt{512MB}$