/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
頂点 1 から頂点 N までの N 頂点からなるグラフの頂点 1 に高橋君がいます。
今このグラフに辺は 1 つも張られていません。
高橋君は以下の操作を繰り返します。
操作 :
- (今高橋君がいる頂点も含めた) N 個の頂点の中から 1 つランダムに選ぶ。各頂点が選ばれる確率は全て \frac{1}{N} であり、選択は操作毎に独立である。
- 今高橋君がいる頂点と選ばれた頂点の間に無向辺を張り、選ばれた頂点に移動する。
グラフが連結になるまでに行われる操作の回数の期待値を求めてください。
制約
- 2 \le N \le 10^5
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
想定解答との絶対誤差または相対誤差が 10^{-6} 以下であれば正解として扱われる。
入力例 1
2
出力例 1
2.00000000000
グラフが連結になるのは、操作において初めて頂点 2 が選ばれた時です。
各 i について i 回目の操作で初めて頂点 2 が選ばれる場合を考えると、答えは \sum_{i = 1}^{\infty} (i \times (\frac{1}{2})^i) = 2 となります。
入力例 2
3
出力例 2
4.50000000000
Score : 400 points
Problem Statement
We have a graph with N vertices called Vertex 1 through N. Takahashi is standing on Vertex 1.
The graph has no edges now.
Takahashi will repeatedly do the following operation:
- Choose one of the N vertices (including the one on which Takahashi is standing now). Every vertex is chosen with probability \frac{1}{N}, independently from previous operations.
- Add an edge between the vertex on which Takahashi is standing now and the chosen vertex, and go to the chosen vertex.
Find the expected value of the number of times he does the operation until the graph becomes connected.
Constraints
- 2 \le N \le 10^5
Input
Input is given from Standard Input in the following format:
N
Output
Print the answer.
Your answer will be considered correct when its absolute or relative error from our answer is at most 10^{-6}.
Sample Input 1
2
Sample Output 1
2.00000000000
The graph becomes connected when the operation chooses Vertex 2 for the first time.
By considering the case Vertex 2 is chosen for the first time in the i-th operation for each i, the answer is \sum_{i = 1}^{\infty} (i \times (\frac{1}{2})^i) = 2.
Sample Input 2
3
Sample Output 2
4.50000000000