洛谷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