Journey

题目描述

我们有一个包含 $N$ 个顶点的图，顶点编号为 顶点 $1$ 到顶点 $N$。Takahashi 站在顶点 $1$。
图当前没有任何边。
Takahashi 将重复执行如下操作：

从 $N$ 个顶点中选择一个顶点（包括 Takahashi 当前所在的顶点）。每个顶点被选择的概率为 $\frac{1}{N}$，各次操作相互独立。 在 Takahashi 当前所在的顶点与所选顶点之间添加一条边，然后走到所选的顶点。

求图变为连通所需操作次数的期望值。

输入格式

输入以标准输入给出，格式如下： $N$

输出格式

输出答案。
当你的答案与我们的答案的绝对或相对误差不超过 $10^{-6}$ 时，将认为是正确的。

2

2.00000000000

3

4.50000000000

提示

$2 \le N \le 10^5$当操作第一次选择到顶点 $2$ 时，图就变为连通。
考虑顶点 $2$ 在第 $i$ 次操作被第一次选择的情况，对于每个 $i$，答案为 $\sum_{i = 1}^{\infty} \bigl(i \times (\frac{1}{2})^i\bigr) = 2$。

标签: AtCoder|abc194D

来源

AtCoder|abc194D