Cocoly1990's Blog

考虑最后的期望值会是多少，设 $f\left(x\right)$ 表示 $n=x$ 时的期望值，那么考虑 $f\left(x\right)$ 如何得到。我们考虑其为 $f\left(x-1\right)$ 多添加 $x$ 得到，那么计算 $x$ 的贡献。显然除非 $x$ 在最后一个，否则不会有任何贡献，$x$ 生成在 $n$ 个位置的概率是相等的，那么有

$f\left(x\right)=\frac{\left(n-1\right)\times f\left(x-1\right)+f\left(x-1\right)+1}{n}= f\left(x-1\right)+\frac{1}{n}$

显然将递推式化简有

$f\left(x\right)=\sum_{i=1}^x \frac{1}{i}$

显然的调和级数，但考虑极限数据 $n=2^{31}$，$\mathcal{O}\left(n\right)$ 的计算会 T 成傻逼。

考虑 $\mathcal{O}\left(1\right)$ 计算调和级数

$\sum_{i=1}^n \frac{1}{i}=\sum_{i=1}^n \int_{i}^{i+1}\frac{1}{\lfloor x \rfloor }dx$

$=\int_{1}^{n+1}\frac{1}{x}+\frac{1}{\lfloor x \rfloor }-\frac{1}{x}dx$

$=\int_{1}^{n+1}\frac{1}{x}dx+\int_{1}^{n+1}\frac{1}{\lfloor x \rfloor }-\frac{1}{x}dx$

$\approx \ln\left(n+1\right)+\gamma$

以上内容转载自该博客。

$\gamma$ 是欧拉常数，其值 $\gamma\approx0.57721566490153286060651209$.

考虑到近似值在数据较小时有精度问题，我们不妨在 $n\leq10^7$ 时 $\mathcal{O}\left(n\right)$ 计算。

#include<bits/stdc++.h>
#define Euler 0.57721566490153286060651209 ;

using namespace std ;
int n ;
double ans ;
int main()
{
	cin >> n ;
	cout << fixed << setprecision(8) ; 
	if(n <= 1e7) 
	{
		for(int i = 1 ; i <= n ; i ++) ans += (1.0 / i) ;
		cout << ans ;
	}
	else cout << log(n + 1) + Euler ;
	return 0 ;
}