题解 P1943 【LocalMaxima】
白鲟
·
·
题解
前言
若出现公式问题可以到博客阅读。
感动于自己推出来一道期望题的式子……
题意简述
求 1~n 的排列中满足大于所有位置在它前面的数的期望个数。
题目分析
首先根据样例盲猜结论：
\operatorname{E}(n)=\sum_{i=1}^n\dfrac{1}{i}
然后我们就可以开始写代码了然后我们需要对这个式子进行证明。易知：
\operatorname{E}(n)=\sum_{i=1}^n\operatorname{P}(i)
其中 \operatorname{P}(i) 表示 i 大于排在它前面的所有数的概率。那么我们要求的就转化为了 \operatorname{P}(i)。
$$
\operatorname{P}(i)=\dfrac{(n-i)!}{(n-i+1)!}=\dfrac{1}{n-i+1}
$$
于是
$$
\operatorname{E}(n)=\sum_{i=1}^n\operatorname{P}(i)=\sum_{i=1}^{n}\dfrac{1}{n-i+1}=\sum_{i=1}^{n}\dfrac{1}{i}
$$
也就是说我们所要求的答案即为第 $n$ 个调和数。但若是直接求和，时间复杂度为 $\operatorname{O}(n)$，对于本题的数据范围而言会超时。我们需要快速计算这个式子。
对于调和数，有一个实用的性质：第 $n$ 个调和数与 第 $n$ 个自然对数的差值收敛于欧拉-马歇罗尼常数 $\gamma$（也叫欧拉常数）。该常数的近似值为 $0.57721566490153285$。这一性质可以记作
$$
\gamma=\lim_{n \to \infty}(\sum_{i=1}^{n}\dfrac{1}{i}-\ln n)
$$
在 $n$ 足够大的时候，我们可以近似地认为
$$
\sum_{i=1}^{n}\dfrac{1}{i}=\gamma+\ln n
$$
那么可以我们根据输入的 $n$ 的大小来选择计算方法，当 $n$ 较小时（可取 $n \le 10^8$）直接计算；当 $n$ 较大时运用这一式子求近似值。
## 代码
```cpp
#include<cstdio>
#include<cmath>
using namespace std;
const long double Gamma=0.5772156649015328;
int n;
long double ans;
int main()
{
scanf("%d",&n);
if(n<=1e8)
for(int i=1;i<=n;++i)
ans+=1.0/i;
else ans=Gamma+log(n);
printf("%.8Lf",ans);
return 0;
}
```