卡特兰数的四个公式
作者:
史一帆
,
2021-10-24 17:08:07
,
所有人可见
,
阅读 404
公式一:递推公式
h(0) = h(1) = 1
h(n) = h(0) ∗ h(n − 1) + h(1) ∗ h(n − 2) + ... + h(n − 1) ∗ h(0) (n >= 2)
如果我们用这个公式显然我们要使用递归算法,那么数据一大就在时空上很麻烦
公式二:递推公式
h(n) = h(n − 1) ∗ (4 ∗ n − 2) / (n + 1)
这个公式应用递推,看上起十分和善
但对大数据呢?
我们注意到大数据的时候h(n)会很大,这时候题目一般会让你对某素数取模(当然你可以打高精度(划掉))
但你在取模过程中难保一个h(n) % mod = 0
那么根据公式下面所有的数都会等于0,于是你就愉快的WA了
公式三:组合数公式一
h(n) = C(2n, n) / (n + 1) (n = 0, 1, 2, ...)
卡特兰数可以与组合数联系起来,得到上面的公式
而组合数就是一个杨辉三角,可以递推得到(这个不属于这道题的讨论范围我假装你们都会(逃))
但我们发现对于大数据你要取模,而对于除法你是没办法用模的性质的(当然你可以应用逆元(划掉)),所以造成了麻烦
公式四:组合数公式二
h(n) = c(2n, n) − c(2n, n − 1) (n = 0, 1, 2, ...)
与组合数公式1不同这个是两个组合数的减法
减法是可以用模的性质的,于是你可以愉快的AC了。