[洛谷P5147]随机数生成器

题目大意：
$$
f_n=
\begin{cases}
\frac{\sum\limits_{i=1}^nf_i}n+1&(n>1)\\
0&(n=1)
\end{cases}
$$
求$f_n(n<2^{31})$

题解：考虑$n>2$时的情况。

$$
f_n=\dfrac{\sum\limits_{i=1}^nf_i}n+1\\
nf_n=\sum\limits_{i=1}^{n-1}f_i+f_n+n\\
\begin{align}
(n-1)f_n=\sum\limits_{i=1}^{n-1}f_i+n\\
(n-2)f_{n-1}=\sum\limits_{i=1}^{n-2}f_i+n-1\\
\end{align}\\
(1)-(2)，得：\\
(n-1)f_n-(n-2)f_{n-1}=\sum\limits_{i=1}^{n-1}f_i+n-(\sum\limits_{i=1}^{n-2}f_i+n-1)\\
(n-1)(f_n-f_{n-1})=1\\
f_n-f_{n-1}=\dfrac1{n-1}
$$

特别的，当$n=2$时，$f_{n-1}$无法用原来的公式来计算，所以$f_n-f_{n-1}$要特别计算，为$2$

当$n>1$时
$$
\begin{align*}
ans&=2+\sum\limits_{i=2}^{n-1}\dfrac1i\\
&=1+\sum\limits_{i=1}^{n-1}\dfrac1i
\end{align*}
$$
但是$n<2^{31}$，无法$O(n)$计算，但是右边的东西（调和级数$H(x)$）在$n$较大时有一个公式：$H_n=\ln(n)+\gamma$。（$\gamma$的定义就是$\gamma=\lim\limits_{n\to\infty}H_n-\ln(n)$，$\gamma=0.57721566490153286060651209008240243104215933593992\dots$）

卡点：无

C++ Code：

#include <cstdio>

#include <cmath>

const int limit = 1000000;

const long double EulerGamma = 0.577215664901532860606512090082;

int n;

long double ans = 1;

int main() {

	scanf("%d", &n);

	if (n == 1) {

		puts("0.00000");

		return 0;

	}

	if (n <= limit) for (int i = 1; i < n; ++i) ans += 1 / static_cast<long double> (i);

	else ans += logl(n - 1) + EulerGamma;

	printf("%.5Lf\n", ans);

	return 0;

}

巴特西

[洛谷P5147]随机数生成器

最新文章

热门文章