BZOJ 4001 概率论

设\(f_i\)表示i个点的二叉树方案数

立刻有\(f_n = \sum_{i=0}^{n-1} f_i f_{n-i-1}\)

设\(F(x)为序列f的生成函数，有F(x)^2 = \sum_{i=0}^{+\infty} \sum_{i+j = n} f_i f_j x^i\)

可设\(g(x) = f(x+1) = \sum_{i+j = x} f_i f_j\)(\(G(x)为序列g的生成函数\))

有: \(G(x) = F(x)^2\)， 又有\(F(x) = xG(x)+f(0)\)，所以解得\(F(x) = (2x)^{-1} (1-(1-4x)^{\frac{1}{2}})\)

有二项式定理展开得\(F(x) = (2x)^{-1} (1-\sum_{i=0}^{+\infty} \dbinom{\frac{1}{2}}{i} (-4)^i)x^i)\)

考虑化简\(\sum_{i=0}^{+\infty} \dbinom{\frac{1}{2}}{i} (-4)^i\)

由组合数定义可知， \(\dbinom{\frac{1}{2}}{i} (-4)^i = -\sum_{i=0}^{+\infty} (2i-1)^{-1} \dbinom{2i}{i}\)

原式化简为\(F(x) = (2x)^{-1} (1+\sum_{i=0}^{+\infty} (2i-1)^{-1} \dbinom{2i}{i})x^i)\)，有后式在x=0时取-1，消去前面的1，然后消去2x，可化简为\(F(x) = \sum_{i=0}^{+\infty} \frac{1}{4i+2} \dbinom{2i+2}{i+1}x^i\)，拆去组合数得\(F(x) = \sum_{i=0}^{+\infty} \frac{1}{i+1} \dbinom{2i}{i} x^i\)，即\(f_i = \frac{1}{i+1} \dbinom{2i}{i}\)

同理设节点数为i的所有二叉树的叶子种数为\(h_i\)(\(H(x)为序列的生成函数\))，\(H(x) = \frac{x}{\sqrt{1-4x}}\)，同理得\(h_i = \dbinom{2i-2}{i-1}\)，可得\(答案=\frac{h_i}{f_i}=\frac{n(n+1)}{2(2n-1)}\)

代码:

#include
    
     #include
     
      #include
      
       using namespace std ;int n; double p ;int main(){    scanf("%d",&n) ;    p = n/1.000000000 ;    printf("%.9lf",((p)*(p+1)) / (2 * (2*p - 1))) ;}