P3978 [TJOI2015]概率論

設$f_i$表示節點數為$i$的二叉樹有多少，$g_i$表示節點數為$i$的二叉樹有多少葉子節點。

$f_n=\sum _{i=0}^{n?1}{f}_i{f}_{n?1?i}$，$f_0=1$。

對于$g$我們枚舉根節點的左兒子或者右兒子，有$g_n=2\sum _{i=0}^{n?1}{f}_i{g}_{n?1?i}$，$g_0=0,g_1=1$。

設$f$的生成函數為$F(x)$，$g$的生成函數為$G(x)$。$F(x)=xF(x)F(x)+1$，$G(x)=2xF(x)G(x)+x$。

解得$F(x)=\frac{2}{1+\sqrt{1?4x}}$，$G(x)=\frac{x}{\sqrt{1?4x}}$。

$(xF(x){)}^{\prime }=\frac{1}{\sqrt{1?4s}}=\frac{G(x)}{x}$。

兩者系數比對一下可以得到$n{f}_{n?1}=g_n$，$\frac{g_n}{f_n}=\frac{n{f}_{n?1}}{f_n}=\frac{(n+1)n}{2(2n?1)}$。

#include <bits/stdc++.h>using namespace std;int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);double n;scanf("%lf", &n);printf("%.10f", (n + 1) * n / (2 * (2 * n - 1)));return 0; }

總結

以上是生活随笔為你收集整理的P3978 [TJOI2015]概率论（生成函数）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。