算法

(期待値の線形性) $O(n)$

题意：你有 $N$ 个节点，高桥现在在一号节点，接下来高桥做以下操作。
在 $N$ 个节点中等概率地选择一个点，并与自己当前所在节点连一条边，然后跳到选择的那个节点。（这是一次操作）
求使得 $N$ 个点联通的期望次数。

分析：假设高桥已经选出了 $S$ 个点，下一步的目标是从 $N$ 个点中选出不存在于 $S$ 中的点。不难看出这件事成功的概率是 $P = \frac{N - S}{N}$。注意到这里服从几何分布，故从 $N - S$ 个点中选出一个点的期望是从 $N - S$ 点中选出一个点的概率的倒数，即 $\frac{N}{N - S}$。

Python 代码

n = int(input())
ans = 0
for i in range(1, n):
    ans += n/(n-i)
print('%.10f' % ans)