D - 旅途

分数: $400$ 分

问题描述

我们有一个包含 $N$ 个顶点的图，分别称为顶点 $1$ 到 $N$。Takahashi 当前位于顶点 $1$。
现在图中没有边。
Takahashi 将重复进行以下操作：

1. 选择一个顶点（包括 Takahashi 当前所在的顶点）。每个顶点被选择的概率是 $\frac{1}{N}$，与先前的操作独立。
2. 在 Takahashi 当前所在的顶点和选择的顶点之间添加一条边，并移动到选择的顶点。

找到直到图变成连通图时，Takahashi 进行此操作的期望次数。

约束

• $2 \le N \le 10^5$

输入

从标准输入中以以下格式给出输入：

$N$

输出

打印答案。
当你的答案与我们的答案的绝对或相对误差不超过 $10^{-6}$ 时，你的答案将被视为正确。

2

2.00000000000

当操作第一次选择顶点 $2$ 时，图变成连通图。
通过考虑顶点 $2$ 第一次在第 $i$ 次操作中被选择的情况，答案为 $\sum_{i = 1}^{\infty} (i \times (\frac{1}{2})^i) = 2$。

3

4.50000000000