自动搬运

查看原文

来自洛谷，原作者为

	NaCly_Fish 北海虽赊，扶摇可接。

搬运于2025-08-24 22:07:38，当前版本为作者最后更新于2019-10-22 13:11:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这题感觉丢到高一数学作业里也没问题吧（

首先我们设那个函数的期望值为 $F(n)$，那么有：

$$F(n)=1+\frac1n\sum\limits_{i=1}^nF(i)$$

移项一下，可以得到

$$\frac{n-1}{n}F(n)=1+\frac1n\sum\limits_{i=1}^{n-1}F(i) $$$$F(n)=\frac{n}{n-1}+\frac{1}{n-1}\sum\limits_{i=1}^{n-1}F(i) $$

然后这样就可以 $\Theta(n)$ 递推计算了。

有了上面的递推式，再搞一下得出通项
( 这里可以先找规律猜结论，用数学归纳法很好证 )

$$F(n)=1+\sum\limits_{i=1}^{n-1}\frac1i$$

后面是调和级数的前 $n-1$ 项和 ( 记为 $h(n-1)$ )，直接算不太好搞，但是有

$$\frac{\text d\ln x}{\text d x}=\frac1x$$

所以 $\ln n$ 和 $h(n)$ 同阶。
进一步地，可以得到：

$$\lim\limits_{n\rightarrow +\infty}h(n)-\ln n \approx 0.57721566490153286 $$

所以 $n$ 很小的时候直接暴力，否则直接用 $\ln (n)$ 来算。

时间复杂度 $\Theta(1)$ ?

代码很简单：

#include<cstdio>
#include<cmath>

int n;
double ans;

int main(){
	scanf("%d",&n);
    if(n<100000) for(int i=1;i<n;++i)  ans += 1.0/i;
    else ans = log(n)+0.577215664901532;
	printf("%.5lf",n==1?0:ans+1);
	return 0;
}