BZOJ 4001 生成函数 概率

求 $ n $ 点二叉树的叶子树期望.

Sol.

设 $ g_n:= n $ 点二叉树形态总数,$ f_n:=n $ 点二叉树叶子的期望数.

有 $ g_n=\sum_ig_ig_{n-1-i},g_0=1, f_n=\sum_i(f_i+f_{n-1-i}){g_ig_{n-1-i}\over g_n}, f_0=1,f_1=1 $ .

求 $g$ 的 OGF $ G $ 有 $ G={1-\sqrt{1-4x}\over 2x} $ .

对 $ f $ 由对称性,移项有 $ f_ng_n=2\sum_if_ig_ig_{n-1-i} $ ,记 $ h_n=f_ng_n $ ,求 $ h $ 的 OGF 有 $ H = 2xHG+x $ 即 $ H=x(1-4x)^{-{1\over2}} $ .

用广义二项式定理展开得 $ [x^{n+1}]H={2n\choose n} $ ,即 $ [x^n]H=h_n={2n-2\choose n-1} $.

同理有 $ [x^n]G=g_n={(2n)!\over(n+1)!n!} $ .

最后 $ f_n={h_n\over g_n}={n(n+1)\over 2(2n-1)} $ .

Code

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

标签: none

添加新评论