OpenJ_POJ1055 Tree

题目链接

题面

以随机父节点的方式生成一棵节点个数不大于 $n$ 的随机树, 求平均结点深度的期望
$n\leq 10^{18}$

题解

又是 Picks 出的题
这题依然是好题
设前面已经生成 $i-1$ 个点,当前生成第 $i$ 个点,这个点的期望深度为 $d_i$ ,前 $i$ 个节点的期望平均深度为 $f_i$ ,则
$$
\begin{eqnarray}
d_i&=&f_{i-1}+1 \tag{1}\\
f_i&=&\frac{f_{i-1}(i-1)+d_i}{i} \tag{2}\\
\end{eqnarray}
$$

将 $(1)$ 式带入 $(2)$ :
$$f_i=\frac{f_{i-1}(i-1)+f_{i-1}+1}{i}=f_{i-1}+\frac{1}{i} $$
所以可以写出 $f_i$ 的通项公式实际上就是
$$ f_n=\sum_{i=1}^{n}\frac{1}{i} $$
其实 $f_n$ 就是调和级数,由于答案是点数不大于 $n$ 的随机树,所以
$$
\begin{eqnarray}
ans&=&\frac{\sum_{i=1}^{n}f_i}{n} =\frac{\sum_{i=1}^{n}\sum_{j=1}^{i}\frac{1}{j}}{n} \\
&=&\frac{\sum_{i=1}^{n}\frac{1}{i}\times (n-i+1)}{n} \\
&=&\frac{(n+1)\sum_{i=1}^{n}\frac{1}{i}-\sum_{i=1}^{n}\frac{i}{i}}{n} \\
&=&\frac{n+1}{n}f_n-1
\end{eqnarray}
$$
所以说只要求出 $n$ 的调和级数
此时有一个做法,对于比较小的 $n$ 通过预处理的方式快速得出 $f_n$
对于很大的 $n$ ,有 $(f_n-\ln{n})$ 收敛于欧拉 – 马斯刻若尼常数,它的近似值为 $\gamma \approx 0.57721566$
所以当 $n$ 很大时可以转换式子
$$ans=\frac{n+1}{n}(\ln{n}+\gamma)-1$$
至此问题已经被解决了

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>

#define reg register
#define MAX_N 1000007
#define MX 1000000
typedef long long ll;

template <typename _T> inline bool read (_T& x) {
    x = 0;
    reg _T y = 1;
    reg char c = getchar();
    while ((c < '0' || '9' < c) && c != EOF) {
        if (c == '-') y = -1;
        c = getchar();
    }
    if (c == EOF) return false;
    while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getchar();
    x *= y;
    return true;
}

ll N;
double f[MAX_N], gm = 0.57721566;

int main () {
    for (int i = 1; i <= MX; ++i)
        f[i] = f[i - 1] + 1 / (double)i;
    while (read(N)) { //(n+1)/n*f_n-1
        if (N <= MX)
            printf("%.8lf\n", (double)(N + 1) / (double)N * f[N] - 1.0);
        else
            printf("%.8lf\n", (double)(N + 1) / (double)N * (std::log((double)N) + gm) - 1.0);
    }
    return 0;
}

引用资料

sys_con

高一 OIer,常规 / 竞赛都渣得不行

发表评论

电子邮件地址不会被公开。 必填项已用*标注