P15121 [ICPC 2024 LAC] Greek Casino

自早期文明以来，人类就一直热衷于碰运气的游戏。即便是以开创性概念“最小公倍数”（LCM）闻名的智慧古希腊人，也无法抗拒一场好的赌博。 受这一数学奇观的启发，雅典的人们设计了一套独特的博彩系统：参与者购买一张票后，会获得随机数量的硬币。为了确定这个数量，设有 $N \ge 3$ 个有序的槽位，编号从 1 到 $N$。一开始，一个令牌被放置在槽位 1，然后重复以下步骤： - 令 $x$ 为令牌当前所在槽位的编号。 - 生成一个介于 1 和 $N$ 之间的随机整数 $y$，并计算 $x$ 和 $y$ 的 LCM，记为 $z$。 - 如果 $z > N$，则过程结束。 - 否则，令牌移动到槽位 $z$，并且参与者获得一枚硬币。 众所周知，庄家总是赢家：赌场采用一种特定的概率分布来生成随机整数，以确保有利可图的结果。 赌场老板不断寻求优化博彩系统的盈利能力。你是一个旨在协助此类任务的人工智能，现给定 $N$ 和概率分布。请确定参与者获得的硬币总数的期望值。

第一行包含一个整数 $N$（$3 \le N \le 10^5$），表示槽位的数量。 第二行包含 $N$ 个整数 $W_1, W_2, \dots, W_N$（对于 $i = 1, 2, \dots, N$，有 $1 \le W_i \le 1000$），表示生成 $i$ 的概率为 $W_i / \left(\sum_j W_j\right)$，即生成 $i$ 的概率是 $W_i$ 相对于整个列表 $W_1, W_2, \dots, W_N$ 之和的相对权重。

输出一行，表示参与者获得的硬币总数的期望值。输出的绝对误差或相对误差不得超过 $10^{-9}$。可以证明，题目描述的过程会在有限次迭代内以概率 1 结束，并且硬币总数的期望值确实是有限的。

翻译由 DeepSeek V3 完成