OI题解 - 概率论(BZOJ) | Lucky_Glass's Blog
0%

OI题解 - 概率论(BZOJ)

不能根据代码量衡量题目难度系列……


# 题意

求 $n$ 个节点的形态不同的(无标号)二叉树的叶子节点数量的期望。

数据规模:$n\le 10^9$


# 解析

看到 $n$ 的规模,大概知道这是道结论题……下面来推一下结论:

从生成函数考虑,因为是无标号,应该是用普通生成函数。

设 $p_i$ 为 $i$ 个节点的二叉树的期望叶子数,那么就要求 $p_n$。再设 $c_i$ 表示 $i$ 个节点的二叉树的数量,显然有 $c_i=\sum_{j=0}^{i-1}c_jc_{i-1-j}$(枚举左右两棵子树的大小)。根据期望的线性性,可以像 DP 一样写出式子:

这个式子的意思就是讨论根的左右子树的大小,分别为 $j$ 和 $(i-j-1)$,那么概率为 $\frac{c_jc_{i-j-1}}{c_i}$,对期望的贡献为 $p_i+p_{i-j-1}$,于是 获得该贡献的概率×贡献 就是期望了。两边同时乘上 $c_i$:

观察到如果把括号展开,则有非常相似的 $c_xp_x$ 形式,于是令 $t_x=c_xp_x$。

可以看到第二个式子是卷积的形式,也就是:

写出这个式子过后,就可以想到生成函数了,设 $T(x),C(x)$ 分别为 $t,c$ 的生成函数:

> Hint

$2xT(x)C(x)$ 中 $T(x)C(x)$ 的第 $i$ 项表示根节点的两棵子树的大小为 $i$ 的方案数,整棵树则需加上根节点,即乘 $x$;

$+x$ 是考虑到只有根节点一个点的情况。

这个式子还可以进一步化简,因为 $C(x)$ 是可以写出式子的。观察递推式 $c_i=\sum_{j=0}^{i-1}c_jc_{i-1-j}$,敏锐的reader可以看出这是一个卡特兰数,可以直接背卡特兰数生成函数的结论,也可以现推(我背不着,所以推导一遍):

把 $C(x)$ 当未知数,其他(包括 $x$)当成常量。

然而我们知道卡特兰数不会有两个解,$\pm$ 一定会舍弃一个。考虑 $\lim_{x\to0}$,如果为 $+$:

(因为是一个大于 $1$ 的数除以无限接近 $0$ 的数)但是我们知道 $c_0=1$,所以 $\lim_{x\to0}C(x)=1$,矛盾。
所以应该取:

顺便写出通项公式:

把 $C(x)$ 代入进去,然后解出 $T(x)$:

然后就是一些奇妙的操作……我也不知道为什么会这么想——把 $\left[xC(x)\right]$ 对 $x$ 求导:

可以发现 $[xC(x)]’=\frac{F(x)}x$。这意味着 $[xC(x)]’$ 和 $\frac{F(x)}x$ 对应项系数相等,即:

emm……真是妙极了


# 源代码

乍一看还以为是 ABC 的前几道水的数学题……

1
2
3
4
5
6
7
8
9
10
11
12
13
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n;

int main(){
scanf("%d",&n);
printf("%.9f\n",(1.0*n*n+n)/(4.0*n-2));
return 0;
}

The End

Thanks for reading!

乱糟糟的感觉