Description

在OI界存在着一位传奇选手——QQ，他总是以风格迥异的搞笑代码受世人围观 某次某道题目的输入是一个排列，他使用了以下伪代码来生成数据 while 序列长度<n do { 随机生成一个整数属亍[1,n] 如果这个数没有出现过则加入序列尾 } 聪明的同学一定发现了，这样生成数据是很慢的，那么请你告诉QQ，生成一个n排列的期望随机次数

Input

一个正整数n，表示需要生成一个n排列

Output

一个数表示期望随机次数，保留整数

---

Sample Input

4

Sample Output

8(.333333…)

【友情提示】

输出样例的括号里表示答案的小数部分，但实际丌要求输出 数学期望=sigma(概率*权值)，本题中为期望随机次数=sigma(概率*随机次数)

Data Constraint

30%数据满足n≤3 80%数据满足n≤10^7 100%数据满足n≤2^31

---

解题思路

定义 Fi 表示序列长度为 i 时的期望随机次数，不难根据题目的定义列出递推式， F(i)=i/n*(F(i)+1)+(n-i)/n*(F(i-1)+1)，解得 F(i)=F(i-1)+n/(n-i) 所以答案为 sigma(n/1+n/2+n/3…+n/n) 这样就可以得到80分。 实际上 1/1+1/2+1/3+…+1/n 为经典的调和级数，当 n 很大的时候，调和级数与自然对数的差约等于欧拉常数，不过 n 较小的时候误差较大 所以当 n 小的时候 O(n)计算该式，当 n 较大的时候，用 ln(n)+欧拉常数近似代替调和级数，但是因为最后答案还乘了 n，所以误差变大，只能精确到整数位。

---

Source Code

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<iomanip> using namespace std; const int N=10000000; int n; void bl() { double m=n; double ans; for (double i=1.0;i<=n;i++) ans+=n/i; long long s=floor(ans+0.50); cout<<s<<endl; } void el() { double c=0.57721566490153286060651209; double ans=log(n)+c; ans*=n; long long s=floor(ans+0.50); cout<<s<<endl; } int main() { scanf("%d",&n); if (n<=N) bl(); else el(); }