【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=2sum_{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{2nchoose 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+1)/(2*(n+n-1)));
	return 0;
}