AT_abc008_3.[ABC008C] コイン

高桥君有 $N$ 枚可以区分正反面的硬币。每枚硬币的大小不同，每枚硬币上都写有一个正整数。

他将这些硬币随机（所有 $N!$ 种排列出现的概率相同）排成一行。然后，执行以下操作：

1. 将所有硬币翻到正面朝上。
2. 从左到右依次处理每一枚硬币，对于当前正在看的硬币，找到其右侧（不包括自身）所有硬币中，硬币上所写整数是当前硬币上整数的倍数的那些硬币，将它们全部翻面。

高桥君想知道，操作结束后正面朝上的硬币数量的期望值。

请你帮高桥君编写程序，计算这个期望值。

输入通过标准输入给出，格式如下：

$N$
$C_1$
$C_2$
$\vdots$
$C_N$

• 第 $1$ 行为一个整数 $N$，表示硬币的数量，$1 \leq N \leq 100$。
• 接下来的 $N$ 行，第 $i$ 行为一个整数 $C_i$，表示第 $i$ 枚硬币上写的正整数，$1 \leq C_i \leq 10^9$。

输出操作结束后正面朝上的硬币数量的期望值。绝对误差或相对误差不超过 $10^{-6}$ 即可。输出末尾需换行。

部分分

本题设置了部分分。

• 对于满足 $N \leq 8$ 的数据集 1，答对可得 $99$ 分。
• 对于无额外限制的数据集 2，答对可再得 $1$ 分，满分 $100$ 分。

样例解释 1

硬币上从小到大分别写着 $2$、$4$、$8$。例如，在 $3!$ 种排列中，若硬币按大小升序排列，则操作如下：

1. 初始时，所有硬币正面朝上，状态为 $[\text{正}, \text{正}, \text{正}]$。
2. 接着，在左起第 $2$ 个及其右侧的硬币中，查找写有 $2$ 的倍数的硬币。左起第 $2$ 个和第 $3$ 个硬币满足条件，将它们翻面，状态变为 $[\text{正}, \text{反}, \text{反}]$。
3. 然后，在左起第 $3$ 个及其右侧的硬币中，查找写有 $4$ 的倍数的硬币。只有左起第 $3$ 个硬币满足条件，将其翻面，状态变为 $[\text{正}, \text{反}, \text{正}]$。

硬币正反变化如下图所示，白色为正面，黑色为反面。

对于全部 $3! = 6$ 种排列，每种排列下最终状态如下图所示。

因此，期望值为 $13/6 = 2.16666666666\ldots$。

样例解释 2

无论排列顺序如何，最终状态总是 $[\text{正}, \text{反}, \text{正}, \text{反}]$。

由 ChatGPT 4.1 翻译