洛谷P3978 [TJOI2015] 概率论 题解

题目链接：P3978 [TJOI2015] 概率论

题意：

为了提高智商，ZJY 开始学习概率论。有一天，她想到了这样一个问题：对于一棵随机生成的 $n$ 个结点的有根二叉树（所有互相不同构的形态等概率出现），它的叶子节点数的期望是多少呢？

判断两棵树是否同构的伪代码如下：

$$\begin{array}{ll} \hline \textbf{算法 1}&\text{Check}(T_1,T_2) \\ \hline 1&\textbf{Require: }\text{ 两棵树的节点 }T_1,T_2\\ 2&\qquad\textbf{if}\ \ T_1=\text{null}\textbf{ or }T_2=\text{null}\textbf{ then }\\ 3&\qquad\qquad\textbf{return}\ \ T_1=\text{null}\textbf{ and }T_2=\text{null}\\ 4&\qquad\textbf{else}\\ 5&\qquad\qquad\textbf{return}\ \text{Check}(T_1\to\mathrm{leftson},T_2\to\mathrm{leftson}) \\ & \qquad\qquad\qquad \textbf{ and }\text{Check}(T_1\to\mathrm{rightson},T_2\to\mathrm{rightson})\\ 6&\qquad\textbf{endif}\\ \hline \end{array}$$

输入格式：

输入一个正整数 $n$，表示有根树的结点数。

输出格式：

输出这棵树期望的叶子节点数，要求误差小于 $10^{-9}$。

数据范围：

对于 $100\%$ 的数据，$1 \le n \le 10^9$。

设 $f_n$ 为 $n$ 个点的本质不同的二叉树的个数，$g_n$ 为这些树的叶子节点数的期望。

这个 $f_n$ 很简单，就是卡特兰数，有 $f_n = \frac{1}{n+1}\binom{2n}{n}$ 。我们考察 $g_n$ 与 $f_n$ 的关系。

打表可知 $g_n = nf_{n-1}$ 。其实证明也不难。

对于每棵 $n$ 个点的二叉树，设它有 $k$ 个叶节点

我们分别把这 $k$ 个叶子删去，会得到 $k$ 棵 $n-1$ 个点的二叉树；

而每棵 $n-1$ 个点的二叉树恰好有 $n$ 个位置可以悬挂一个新的叶子，

那么每棵 $n-1$ 个点的二叉树被得到了 $n$ 次，即 $g_n = nf_{n-1}$ 。

于是 $g_n = \frac{n(n+1)}{2(2 n-1)}$ ，这道题就做完了

时间复杂度 $\mathcal{O}(1)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)())


signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n; cout << fixed << setprecision(12);
    cout << 1.0 * n * (n + 1) / (2 * (2 * n - 1)) << '\n';
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/article/44gxsxg0