BZOJ 4001 概率论 解题报告

4001: [TJOI2015]概率论

Time Limit: 10 Sec  Memory Limit: 128 MB

Description

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

算法1：bool Check(T1, T2)
         Require：两棵树的节点T1, T2
                  if T1==null || T2==null then
                          return T1==null && T2==null
                  else
                          return Check(T1->leftson, T2->leftson) && Check(T1->rightson, T2->rightson)
                  end if

Input

输入一个正整数$N$，代表有根树的结点数

Output

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

Sample Input

1

Sample Output

1.000000000

HINT

$1\leqslant N\leqslant10^9$

Solution

设$\mathrm P(x)$表示$x$个节点的二叉树叶子节点数的期望，$f_x$为$x$个节点可构成的不同二叉树的数量，$s_x$为$x$个节点构成的所有不同二叉树的叶子节点的和。由期望的定义可得，$\mathrm P(x)=\frac{s_x}{f_x}$。

$f_x$的求法是一个经典的卡塔兰数问题：固定某个点为根节点，设其左子树有$a$个节点，右子树有$b$个节点，在此条件下，不同的二叉树的数量等于$f_af_b$。而对于$f_x$，$a+b=x-1$且$0\leqslant a\leqslant x-1$。即： $$f_x=\sum_{i=0}^{x-1}f_i\cdot f_{x-1-i}$$

显然$f_x$是第$x$个卡塔兰数（参见https://en.wikipedia.org/wiki/Catalan_number）。于是，$f_x=\frac1{x+1}\begin{pmatrix}2x\\x\end{pmatrix}$。

我们用相似的方式推导$s_x$的递推式：

固定某个点为根节点，设其左子树有$a$个节点，右子树有$b$个节点，我们首先这考虑左子树对$s_x$的贡献，所有不同的左子树的叶子节点的数量和为$s_a$，每种方案都可以和一个右子树结合得到一棵不同形态的二叉树，结合的方案数为$f_b$，所以左子树对$s_x$的贡献为$s_af_b$。类似地，左右子树的总贡献为$s_af_b+f_as_b$。又因为$a+b=x$，所以： $$s_x=\sum_{i=0}^{x-1}(s_i\cdot f_{x-1-i}+f_i\cdot s_{x-1-i})=2\sum_{i=0}^{x-1}s_i\cdot f_{x-1-i}$$

参考卡塔兰数通项公式的推导，我们采用母函数计算$s_x$的通项公式。

我们首先确定$s_0$的值，由于$s_1=2f_0s_0=1$，$s_2=2s_0f_1+2s_1f_0=2$，我们发现$s_0$无论取和值都无法满足条件。于是我们大胆猜测，$s_x$的递推式不适用于第一项。这样，$s_0=0$。

根据普通母函数的定义，设： $$g(x)=\sum_{n=0}^\infty s_nx^n$$ $$h(x)=\sum_{n=0}^\infty f_nx^n$$

展开，有 $$g(x)=s_0+s_1x+s_2x^2+s_3x^3+...$$ $$h(x)=f_0+f_1x+f_2x^2+f_3x^3+...$$

考虑母函数与递推式的联系： $$g(x)h(x)=s_0f_0+(s_0f_1+s_1f_0)x+(s_2f_0+s_1f_1+s_0f_2)x^2+...$$

整理，得： $$g(x)h(x)=\sum_{i=0}^0s_if_{0-i}+(\sum_{i=0}^1s_if_{1-i})x+(\sum_{i=0}^2s_if_{2-i})x^2+...$$

根据$s_x$的递推式： $$xg(x)h(x)=\sum_{i=0}^0s_if_{0-i}x+(\sum_{i=0}^1s_if_{1-i})x^2+(\sum_{i=0}^2s_if_{2-i})x^3+...$$ $$2xg(x)h(x)=0+s_2x^2+s_3x^3+...$$

即： $$2xg(x)h(x)=g\left(x\right)-s_1x$$

结合卡塔兰数的推导： $$\left\{\begin{array}{l}2xg(x)h(x)=g\left(x\right)-x\\xh(x)^2=h(x)-1\end{array}\right.$$

解得： $$\left\{\begin{array}{l}g(x)=\frac x{\sqrt{1-4x}}\\h(x)=\frac{1-\sqrt{1-4x}}{2x}\end{array}\right.,\left\{\begin{array}{l}g(x)=-\frac x{\sqrt{1-4x}}\\h(x)=\frac{1+\sqrt{1-4x}}{2x}\end{array}\right.$$

不妨令$g(x)=\frac x{\sqrt{1-4x}} =x(1-4x)^{-\frac12}$，根据二项式定理： $$g(x)=x\sum_{n=0}^\infty\begin{pmatrix}-\frac12\\n\end{pmatrix}\left(-4x\right)^n$$ $$g(x)=x\sum_{n=0}^\infty\frac{(-{\displaystyle\frac12})\times(-{\displaystyle\frac32})\times...\times(-{\displaystyle\frac12}-i+1)}{n!}\left(-4x\right)^n$$

$$g(x)=x\sum_{n=0}^\infty\frac{1\times3\times...\times(2n-1)}{n!}2^nx^n$$

$$g(x)=x\sum_{n=0}^\infty\frac{(2n)!}{n!\cdot n!} x^n$$

$$g(x)=x\sum_{n=0}^\infty\begin{pmatrix}2n\\n\end{pmatrix}x^n$$

$$g(x)=\sum_{n=1}^\infty\begin{pmatrix}2n-2\\n-1\end{pmatrix}x^n$$

所以 $$s_x=\begin{pmatrix}2x+2\\x+1\end{pmatrix}$$

     得到了$s_x$的通项公式。我们可以一眼看出$\mathrm P(x)=\frac{x^2+x}{4x-2}$。

       代码一分钟，公式一下午！

:(