青春须早为，岂能长少年。这篇文章主要讲述BZOJ 4001[TJOI2015]概率论相关的知识，希望能为你提供帮助。
1.其实这是一个纯数学题。??题目链接??。额，网上很多人都说好猜出来，这个我是不敢苟同，至少我觉得我是猜不出来，打表也打不出来。因为毫无规律可言。
2.其实这个题就是再说n个节点的二叉树叶子节点的期望是多少，ans=n*(n+1)/(2*(2*n-1))，n是节点个数。首先n个节点的二叉树种类是C_n个，C就是卡特兰数，这个题其实算一下所有的叶子节点有多少个就行了.但是很难算。考虑DP[i][j]代表i个节点，j个叶子的期望，那么转移很简单，但是无法优化，所以不是正解。??这里是正解??。推导看起来不是很容易，里面有一步大佬没有给出详细过程，于是有了这篇博客。
就是这里，Catalan数的递推人尽皆知，但是生成函数好像很突兀就出来了，至于怎么来的，下面来推导一下。
前置技能：生成函数。二项式求和常见公式等。
首先考虑一个很经典的问题：汉诺塔问题。如果有n个盘子，那么移动的次数就是2^n-1.（这里的柱子默认是三根）。这个是怎么来的呢？递推公式啊！（大喊），是的，的确实从递推公式推出来的。但是为了前置知识，还是回顾一下它是怎么来的。
（1）假设hn为n个盘子需要移动的最小次数
（2）开始操作，首先把n-1个移动到另外一个柱子上，这使用hn-1次，然后移动最下面的大盘子，+1次，再把n-1个拿回来,+hn-1次。所以显然递推公式：
这个就是高中数列求和了，直接俄求和就可以得到hn的表达式。
现在考虑hn这个数列，h0,h1,h2,....hn,设g(x)为h数列的生成函数。
对g(x)操作一下：
两式相减，可以解出g(x):
把g(x)列项，并泰勒展开可得：
到了这里，根据生成函数第n项系数的含义，就知道hn=pow(2,n)-1.
其实这个化简唯一有技巧的地方就在于对g(x）的配凑，然后把关于h的全部消掉。这里为啥会乘-2x啊，其实并不是空想的，从递推公式来的。
那么现在，如何求卡特兰数的生成函数呢？
好像，递推公式，和上一个不太像啊？
继续沿用刚才的符号，假设hn代表第n项卡特兰数的值，hn的递推公式：
g(x)为hn的生成函数：
这个时候，观察hn的表达式，它是有它前边的n-1项确定的，再仔细发现一下，就可以看见，j+n-1-j=n-1.完了，看到这里惊为天人，这不就是卷积的定义？多项式乘法？FFT？循环卷积？的确是这样的，这也就是接下来的推导的Core。
将g(x)做乘方：
可以发现，卷积完之后，每一项系数都是该次数对应的Catalan数，所以在化简一下：
因为h1=h2=1,所以为了统一，把h1换为h2，那么就可以得到：
这个式子就和g(x)有一项只差，就差了h1.所以也可以写作：
这是一个函数方程，把g(x)看作y解一元二次方程，就可以得到题解中的，
g(0)=0，会排除一个答案。所以答案只有一个。但这里就和大佬的题解衔接上了，其实这个题要是真的推，还是蛮困难的。如果知道了很多中间结论，哪会快很多。
【BZOJ 4001[TJOI2015]概率论】
推荐阅读
- Webpack的基本使用
- KNN算法
- WebpackTypeError: Cannot read property ‘tap‘ of undefined at HtmlWebpackPlugin.
- 垃圾回收算法以及垃圾回收器
- Spring基础
- HDU5017模拟退火求距离最值
- JAVA 虚拟机的内存模型
- HDU1724自适应Simpson积分
- 头条后端面试