真的不能再拖了，学的新知识必须得总结，没能力还懒得总结，只能水过地皮干。
数论很多，按专题分成几部分，这里是第一部分。
部分内容来自学长。

Catalan数

梳理

定义：

\(n\)个不同的数依次进栈，其出栈序列的种类数

我们设\(f[t]\)表示\(t\)个数依次进栈，其出栈序列的个数
首先显然f[0]=1；
那么我们拿出一个数\(a\)，设他被压入之后有\(i\)个数曾经被压入过，显然这些数在\(a\)弹出前定已弹出，那么这些数的方案数为\(f[i]\)
那么除了\(a\)和曾经压在\(a\)上的数 进出的方案数和之前的\(f[i]\)是不互相影响的，这些方案的总数为\(f[n-i-1]\)
有没有很熟悉？
没错，因为数\(a\)是随便拿的，所以\(i\)可以取\(0\dots n-1\)中的任何一个数，再来表示我们的思路，就有：

也就是\(Catalan\)数的递归定义。

长度为\(2n\)的合法括号序列数

将一个(视为入栈，一个)视为出栈，就转化成了上一个问题。

圆上有\(2n\)个不同的点两两连接，连出的弦均不相交的方案数

把连线看成有向边，每个起点视为入栈，每个终点视为出栈即与前证同理。

从\((0,0)\)走到\((n,n)\)(只能向上或向右),不越过对角线的方案数

向右走视为入栈，向上走视为出栈，即与前证同理。

凸\(n\)边形\((n\geq 3)\)的三角划分数

这个不太一样。
设凸\(t\)边形\((t\geq 3)\)的三角划分数为\(f[t-2]\)
显然\(f[0]=f[1]=1\);（\(f[0]\)是我们这里特别规定的）
我们搞一个三角形出来，凸\(n\)边形没被划分部分就分成两个新多边形，设一组是\(i\)边形，则另一组是\(n-i-1\)边形，那么此时有\(f[i]*f[n-i-1]\)种方案。
总方案数就是：

阶梯的矩形划分数

以一个阶为顶点做矩形，则剩下的阶被分成了\(i\)个和\(n-i-1\)个。
其他可以自行理解。

\(n\)个不同的节点组成的有根二叉树的方案数

这个比较简单。
设以一个结点为根的子树大小为\(t\)，这个子树的方案为\(f[t]\)
设根节点的左子树大小为\(i\)，则右子树大小为\(n-i-1\)
其他可以自行理解。

有趣的数列

我们把所有数从小到大依次放入，把奇数位和偶数位分开，那我们在往里加东西的时候肯定是挑第一个空位加。
如果当前奇数位上数的个数大于偶数位上数的个数，就不合法。
抽象一下，既然合法时奇数位上数的个数不大于偶数位上数的个数，就可以抽象成前面那个不越过对角线的问题。
于是答案就是卡特兰数，数据范围大得写高精，这里用\(\frac{C_{2n}^{n}}{n+1}\)加分解质因数就比较方便

树屋阶梯

裸题，可以参考前面阶梯的矩形划分数一节

【刷题笔记】数论们（一）

原文：https://www.cnblogs.com/zzzuozhe-gjy/p/12835551.html