問題文
高桥可以区分正反面。 我有 N 硬币。硬币大小不同,每枚硬币都有 1 正整数被一一写入。
随机分配这些硬币(N! 将组合排列成一行,使它们具有相同的概率。然后执行以下步骤:
- 将所有硬币正面朝上。
- 从最左边的硬币开始,翻转当前查看的硬币右侧的所有硬币(不包括其本身),这些硬币上写有当前查看的硬币上写的整数的倍数。
高桥先生想知道完成此操作后正面朝上的硬币数量的预期值。
我希望你创建一个程序来计算高桥君处的期望值。
入力
输入将以以下形式从标准输入给出。
N C_1 C_2 : C_N
- 1 行包含一个代表硬币数量的整数。 来自行 N (1 ≦ N ≦ 100) 被给予。
- 2 从行 N 行数过多 在 i (1 ≦ i ≦ N) 行中,i 最大硬币上写的整数 写入 C_i (1 ≦ C_i ≦ 10^9) 。
部分点
针对此问题设置了部分分数。 满足
- N ≦ 8 的数据集 如果您正确回答 1 , 给出99 点。
- 没有附加约束的数据集 如果您正确回答 2 ,那么 1 给出积分,总分 获得 100 点。
出力
打印正面朝上的硬币数量的预期值。绝对误差或相对误差 10^{-6} 或更少是可以接受的。还在输出末尾添加换行符。
入力例1
3 2 4 8
出力例1
2.166666666667
每枚硬币的尺寸按从最小到最小的顺序排列。 写入数字 2 , 4 , 8 。例如,3! 如果硬币按大小升序排列,则将执行以下步骤。
- 初始状态下,所有硬币都是正面朝上,所以从左边开始,硬币是[
表,表,表]。 - 接下来,从左边开始 2 之后的币种中,
寻找上面写有2 倍数的硬币。从左边开始
从左起第 2 枚硬币
第 3 枚硬币适用,因此翻转这些硬币。结果,硬币是[
表,裏,裏]。 只有第 - 接下来,从左边开始 3 之后的币种中,
寻找上面写有4 倍数的硬币。从左边开始
从左起第 3 枚硬币是相关的,因此翻转这枚硬币。结果,硬币是[
表,裏,表]。 只有第
硬币的两面变化如下图所示。在此图中,白色硬币表示为面朝上的硬币,黑色硬币表示为面朝下的硬币。

这样,3! = 6 每条街道排列的最终状态如下图所示。

由上可知,期望值为 13/6 = 2.16666666666... 。
入力例2
4 5 5 5 5
出力例2
2.000000000000
无论你怎么排列,从左到右,[表, 裏, 表, 裏]。
只有第
入力例3
5 2 3 2 6 12
出力例3
3.100000000000