分数: 400 点
问题陈述
我们有一个图表 N 名为 Vertex 的顶点 1 通过 N。高桥站在顶点 1.
该图现在没有边。
高桥会重复执行以下操作:
- 选择其中一项 N 顶点(包括高桥现在站立的顶点)。每个顶点都是按概率选择的 \frac{1}{N},独立于之前的操作。
- 在高桥现在站立的顶点和所选顶点之间添加一条边,然后转到所选顶点。
求他执行该操作直到图形连通的次数的期望值。
约束
- 2 \le N \le 10^5
输入
输入由标准输入按以下格式给出:
N
输出
打印答案。
当您的答案与我们答案的绝对或相对误差最多为 10^{-6}.
示例输入 1
2
示例输出 1
2.00000000000
当操作选择“顶点”时,图变为连通 2 第一次。
通过考虑 Vertex 的情况 2 首次被选中 i每个的第次操作 i,答案是 \sum_{i = 1}^{\infty} (i \times (\frac{1}{2})^i) = 2.
示例输入 2
3
示例输出 2
4.50000000000