← 返回题目列表

AtCoder · abc194_d

D. 旅程

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

我们有一个图表 N 名为 Vertex 的顶点 1 通过 N。高桥站在顶点 1.
该图现在没有边。
高桥会重复执行以下操作:

  1. 选择其中一项 N 顶点(包括高桥现在站立的顶点)。每个顶点都是按概率选择的 \frac{1}{N},独立于之前的操作。
  2. 在高桥现在站立的顶点和所选顶点之间添加一条边,然后转到所选顶点。

求他执行该操作直到图形连通的次数的期望值。

约束

  • 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