BZOJ4001【TJOI2015】概率论 <生成函数>

Problem

【TJOI2015】概率论

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

Input

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

Output

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

Sample Input

1

Sample Output

1.000000000

Hint

$1\le N\le10^9$

标签：生成函数

Solution

生成函数结论题。

1. 构造递推式

考虑用$f_i$表示$i$个结点的树的所有形态中叶子结点的个数和，用$g_i$表示$i$个结点的树的所有形态数。则叶子个数的期望为$\frac{f_i}{g_i}$。

首先计算$g_i$。对于$i$个结点的二叉树，去掉根后还剩$i-1$个结点，若左子树中有$j$个结点，则右子树中有$i-j-1$个结点，可知左子树有$g_j$种形态，右子树有$g_{i-j-1}$种形态，因此此种情况下树的形态数为$g_j\times g_{i-j-1}$。故有$g_i=\sum_{j=0}^{i-1}g_jg_{i-j-1}$。
然后计算$f_i$。对于$i$个结点的二叉树，若左子树中有$j$个结点，右子树中有$i-j-1$个结点，可知叶子结点个数和会增加$f_j\times g_{i-j-1}$。于是有$f_i=\sum_{j=0}^{i-1}f_jg_{i-j-1}$。

2. 构造生成函数

补充定义$f_0=1,g_0=1$构造$f,g$的生成函数：

$$F(x)=f_0x^0+f_1x^1+\cdots+f_ix^i+\cdots\\ G(x)=g_0x^0+g_1x^1+\cdots+g_ix^i+\cdots\\$$

对于$G(x)$，有$G^2(x)=g_0^2x^0+(g_0g_1+g_1g_0)x^1+\cdots+\sum_{j=0}^{i}g_jg_{i-j}x_i+\cdots$，于是$G(x)=G^2(x)+1$。同理，对于$F(x)$，将$F(x)G(x)$展开后与$F(x)$比较，可得$F(x)=2xF(x)G(x)+1$。

由此，解二次方程

$$\begin{cases} F(x)=2xF(x)G(x)+1\\ G(x)=G^2(x)+1\\ \end{cases}$$

可得

$$\begin{cases} F(x)=\frac{x}{\sqrt{1-4x}}\\ G(x)=\frac{1-\sqrt{1-4x}}{2x}\\ \end{cases}$$

（已根据带入$x=1$后得出结果的正负性舍去每个函数的另一种取值。）

3. 解递推式通项

接下来用广义二项式定理展开$\sqrt{1-4x}$并求出$f,g$的通项。

定义广义下的二项式系数$\binom{\alpha}{k}\;(\alpha\in\R,k\in\Z^*)$为

$$\binom{\alpha}{k}=\frac{\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-k+1)}{k!}$$

有定理

$$(x+y)^\alpha=\sum_{i=0}^{\infty}\binom{\alpha}{i}x^{\alpha-i}y^i$$

则有特殊形式

$$\sqrt{1+x}=(1+x)^\frac{1}{2}=\sum_{i=0}^{\infty}\binom{\frac{1}{2}}{i}x^i\\ \frac{1}{\sqrt{1+x}}=(1+x)^{-\frac{1}{2}}=\sum_{i=0}^{\infty}\binom{-\frac{1}{2}}{i}x^i\\$$

因此

$$F(x)=x\sum_{i=0}^{\infty}\binom{-\frac{1}{2}}{i}(-4)^ix^i\\\\ G(x)=\frac{1-\sum_{i=0}^{\infty}\binom{\frac{1}{2}}{i}(-4)^ix^i}{2x}\\$$

分别化简两个函数中带广义二项式系数的系数

$$\begin{aligned} \binom{-\frac{1}{2}}{i}(-4)^i &=\frac{-\frac{1}{2}(-\frac{1}{2}-1)(-\frac{1}{2}-2)\cdots(-\frac{1}{2}-i+1)}{i!}(-4)^i\\ &=\frac{-1(-1-2)(-1-4)\cdots(-1-2i+2)}{i!}(-2)^i\\ &=(-1)^i\frac{-1(-1-2)(-1-4)\cdots(-1-2i+2)}{i!}2^i\\ &=\frac{1\times3\times5\times\cdots\times(2i-1)}{i!}\times\frac{2\times4\times6\times\cdots\times2i}{i!}\\ &=\frac{(2i)!}{i!i!}\\ &=\binom{2i}{i}\\ \binom{\frac{1}{2}}{i}(-4)^i &=\frac{\frac{1}{2}(\frac{1}{2}-1)(\frac{1}{2}-2)\cdots(\frac{1}{2}-i+1)}{i!}(-4)^i\\ &=\frac{1(1-2)(1-4)\cdots(1-2i+2)}{i!}(-2)^i\\ &=(-1)^i\frac{(1-2)(1-4)\cdots(1-2i+2)}{i!}\times2^i\\ &=-\frac{1\times3\times5\times\cdots\times(2i-3)}{i!}\times\frac{2\times4\times6\times\cdots\times2i}{i!}\\ &=-\frac{(2i)!}{(2i-1)i!i!}\\ &=-\frac{1}{2i-1}\binom{2i}{i}\\ \end{aligned}$$

分别带回原生成函数得

$$\begin{aligned} F(x) &=x\sum_{i=0}^{\infty}\binom{-\frac{1}{2}}{i}(-4)^ix^i\\ &=x\sum_{i=0}^{\infty}\binom{2i}{i}x^i\\ &=\sum_{i=1}^{\infty}\binom{2i-2}{i-1}x^i\\ &=\sum_{i=1}^{\infty}\frac{i^2}{2i(2i-1)}\binom{2i}{i}x^i\\ &=\sum_{i=1}^{\infty}\frac{i}{2(2i-1)}\binom{2i}{i}x^i\\ G(x) &=\frac{1-\sum_{i=0}^{\infty}\binom{\frac{1}{2}}{i}(-4)^ix^i}{2x}\\ &=\frac{1+\sum_{i=0}^{\infty}\frac{1}{2i-1}\binom{2i}{i}x^i}{2x}\\ &=\frac{\sum_{i=1}^{\infty}\frac{1}{2i-1}\binom{2i}{i}x^{i-1}}{2}\\ &=\sum_{i=0}^{\infty}\frac{1}{2(2i+1)}\binom{2i+2}{i+1}x^{i}\\ &=\sum_{i=0}^{\infty}\frac{1}{2(2i+1)}\cdot\frac{(2i+1)(2i+2)}{(i+1)^2}\binom{2i}{i}x^{i}\\ &=\sum_{i=0}^{\infty}\frac{1}{i+1}\binom{2i}{i}x^{i}\\ \end{aligned}$$

因此有通项

$$\begin{cases} f_i=\frac{i}{2(2i-1)}\binom{2i}{i}\\ g_i=\frac{1}{i+1}\binom{2i}{i}\\ \end{cases}$$

综上，可得答案$Ans=\frac{f_n}{h_n}=\frac{n(n+1)}{4n-2}$。

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    double n; scanf("%lf", &n);
    printf("%.9lf\n", n*(n+1)/(4*n-2));
    return 0;
}