【BZOJ4001】[TJOI2015]概率论(生成函数)

【BZOJ4001】[TJOI2015]概率论(生成函数)

题面

BZOJ

洛谷

题解

这题好仙啊。。。。

设\(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;
}
上一篇:WinForm - 格式化DataGridView单元格数据


下一篇:通知url必须为直接可访问的url,不能携带参数 异步接收微信支付结果通知的回调地址 不能携带参数。 回调地址后是否可以加自定义参数 同步回调地址 异步回调地址 return_url和notify_url的区别