做暧暖的免费网站,网站小程序开发公司,服务商类型是什么意思,wordpress付费閱讀插件P3978 [TJOI2015]概率论
设fif_ifi表示节点数为iii的二叉树有多少#xff0c;gig_igi表示节点数为iii的二叉树有多少叶子节点。 fn∑i0n−1fifn−1−if_n \sum\limits_{i 0} ^{n - 1}f_if_{n - 1 - i}fni0∑n−1fifn−1−i#xff0c;f01f_0 1f01。
对于g…P3978 [TJOI2015]概率论
设fif_ifi表示节点数为iii的二叉树有多少gig_igi表示节点数为iii的二叉树有多少叶子节点。
fn∑i0n−1fifn−1−if_n \sum\limits_{i 0} ^{n - 1}f_if_{n - 1 - i}fni0∑n−1fifn−1−if01f_0 1f01。
对于ggg我们枚举根节点的左儿子或者右儿子有gn2∑i0n−1fign−1−ig_n 2\sum\limits_{i 0} ^{n - 1}f_ig_{n - 1 - i}gn2i0∑n−1fign−1−ig00,g11g_0 0, g_1 1g00,g11。
设fff的生成函数为F(x)F(x)F(x)ggg的生成函数为G(x)G(x)G(x)。F(x)xF(x)F(x)1F(x) xF(x)F(x) 1F(x)xF(x)F(x)1G(x)2xF(x)G(x)xG(x) 2xF(x)G(x) xG(x)2xF(x)G(x)x。
解得F(x)211−4xF(x) \frac{2}{1 \sqrt{1 - 4x}}F(x)11−4x2G(x)x1−4xG(x) \frac{x}{\sqrt{1 - 4x}}G(x)1−4xx。
(xF(x))′11−4sG(x)x(xF(x)) \frac{1}{\sqrt{1 - 4s}} \frac{G(x)}{x}(xF(x))′1−4s1xG(x)。
两者系数比对一下可以得到nfn−1gnnf_{n - 1} g_nnfn−1gngnfnnfn−1fn(n1)n2(2n−1)\frac{g_n}{f_n} \frac{nf_{n - 1}}{f_n} \frac{(n 1)n}{2(2n - 1)}fngnfnnfn−12(2n−1)(n1)n。
#include bits/stdc.husing 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;
}
