卡特兰数最常见的描述就是2n个球进站出站有多少种顺序
推导：折线法，问题转化为从 (0,0)到(2n,0)每次可以向右上或者右下走一波，问在不越过 y=0这条线的情况下，有多少种走法。
【数论|卡特兰数公式推导】
文章图片
所以可以根据总数减去非法数
总数很明显是 cn2n
非法数可以这样算。如果这个过程非法，这条线一定会碰到 y=?1这样我们可以取折线第一次喷到直线 y=?1 的点。然后的折线对 y=?1 做对称，这样所有的点最终都会汇聚到 (2n,?2) 这样总数就有 Cn?12n
所以最终结果就是 cn2n?Cn?12n
化简后很容易得到 cn2nn+1
推荐阅读
- HDU 5528【2015长春现场赛 B】 Count a * b
- 类欧几里得算法|[类欧几里得算法 数论] BZOJ 2987 Earthquake
- [数论] Codeforces 819D R #421 D.Mister B and Astronomers & 516E R #292 E. Drazil and His Happy Friends
- 模板 poj2947 Widget Factory 高斯消元
- 【扩展欧几里得】练习题
- 扩展欧几里得【数论
- 数论|hdu 5322 Hope（分治+NTT）
- HDU 5528 Count a × b
- 线性同余方程组
- 数论|AtCoder Beginner Contest 156 C.Rally