【BZOJ4001】[TJOI2015]概率论(生成函数)
题面
题解
这题好仙啊。。。。
设\(g_n\)表示\(n\)个点的二叉树个数,\(f_n\)表示\(n\)个点的二叉树的叶子个数。
最终要求的东西就是\(\frac{f_n}{g_n}\)。
考虑这个玩意怎么转移,先考虑二叉树个数,即怎么求\(f_n\)。
每次我们认为新加入的点作为根节点,那么接下来只需要枚举其左右子树大小就行了,所以得到:
\[g_n=\sum_{i=0}^{n-1}g_ig_{n-1-i}
\]
\]
然后考虑怎么求\(f\),我们还是可以枚举一侧的左子树大小,那么只考虑左子树的叶子节点个数,这样子乘上右侧的方案数就是答案。然后左右还可以交换。所以有:
\[f_n=2\sum_{i=0}^{n-1}g_if_{n-1-i}
\]
\]
设\(G(x)\)为\(g\)的生成函数,得到:\(G(x)=G(x)^2x+1\),解出来\(G(x)=\frac{1-\sqrt{1-4x}}{2x}\)。
类似的,\(F(x)=2G(x)F(x)x+x\),解出来\(F(x)=\frac{x}{1-2G(x)x}\)。
再把\(G(x)\)带进去,可以解出来\(F(x)=\frac{x}{\sqrt{1-4x}}\)。
发现\((xG(x))'=\frac{1}{\sqrt{1-4x}}=\frac{F(x)}{x}\),进一步可以得到\(f_n=g_{n-1}\)。
然后\(g\)是卡特兰数,所以得到通项\(\frac{2n\choose n}{n+1}\)。
然后答案就是\(\frac{n(n+1)}{2(2n+1)}\)了。
#include<cstdio>
using namespace std;
int main()
{
double n;scanf("%lf",&n);
printf("%.9lf\n",n*(n+1)/(2*(n+n-1)));
return 0;
}