概要
(Catalan)数的递推式：
(Catalan)数的递推解（通项式）：
(Catalan)数的前五项：(1,1,2,5,14)。
(Catalan)数在(OEIS)上：A000108
应用
没有什么用的东西说完了，我们来讨论它的应用：
合法路径：从((0,0))到((n,n))，只能向右或向上且不能越过(y=x)，求路径数。
证明：不考虑不越过(y=x)的限制，方案数为(egin{pmatrix} 2n \ n \ end{pmatrix})，越过(y=x)的方案数等价于((-1,1))到((n,n))的方案数（路径沿(y=x+1)对称），为(egin{pmatrix} 2n \ n-1 \ end{pmatrix})，与((4))式相同。
合法括号序列：(n)个左括号，(n)个右括号，求组成的合法括号序列。原题
与合法路径等价。
出栈序列：进栈序为(1,2,dots,n)，求出栈序计数。原题
进栈为左括号，出栈为右括号，即与合法括号序列等价。
二叉树计数：给定(n)个节点，求不同的二叉树种数。
左儿子为左括号，右儿子为右括号，考虑(dfs)序，与合法括号等价。
凸多边形划分：将一个凸多边形连接若干不相交的对角线划分的方案数。((C_{n-2}))
容易看出递推形式与((1))相同。
扩展(Catalan)数：(n)位(01)串，(m)个(0)，前缀(1)的个数不少于(0)，求计数。原题
和合法路径的证明方式基本一致，即由((0,0))到((n-m, m))的路径数减去((-1,1))到((n-m, m))的路径数。
例题
然后就是一些很裸的例题。
答案是(Catalan)数，可以由手推前四项基本得出。
如何推导？对于大小为(n)的阶梯，在上面切掉一个大小为(i（iin [0,n])的阶梯，在右边切掉一个大小为(n-i+1)的阶梯，中间放一个矩形，一共为(i+(n-i+1)+1=n)个矩形。不难发现这是((1))式。
可是我们需要高精度，我不想写高精怎么办？
于是就有了下面这份代码：
n=int(input())
ans=1
for i in range(n+2, n*2+1):
ans*=i
for i in range(1, n+1):
ans//=i
print(ans)
(python)大法好！
这个题应该是最有趣的一个。
首先打表（或手推）找规律肯定是一种省时省力的方法。
考虑推导：把(1-2n)依次放入数列，每次放在奇数位或偶数位的最前面一个。任何时候奇数位个数不少于偶数位，等价于合法括号。
但这个题还有一个问题：模数不为质数。这意味着我们不能常规地求逆元得到答案。
考虑质因数分解，因为(C_n=frac{prod_{i=n+2}^{2n}}{prod_{i=1}^{n}})，于是可以这么写。
//线筛b[i]
rep(i, 1, n) cnt[i]=-1;//分母
rep(i, n+2, n<<1) cnt[i]=1;//分子
per(i, n<<1, 2) if (b[i]<i) //b[i]为i的一个质因数
cnt[b[i]]+=cnt[i], cnt[i/b[i]]+=cnt[i];
rep(i, 2, n<<1) if (b[i]==i) ans=1ll*ans*Pow(i, cnt[i])%P;
复杂度是什么？预处理线筛(O(n))，分解(O(n))，统计答案(O(pi (n)cdot log(n))approx O(frac{n}{ln(n)}cdot log(n))approx O(n))，所以总复杂度为(O(n))
完整代码：
#include<cstdio>
#define rep(i, a, b) for (register int i=(a); i<=(b); ++i)
#define per(i, a, b) for (register int i=(a); i>=(b); --i)
using namespace std;
const int N=2000005;
int p[N], b[N], cnt[N], n, P, ans=1, tot;
inline int read()
{
int x=0,f=1;char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
return x*f;
}
int Pow(int x, int t)
{
int res=1;
for (; t; t>>=1, x=1ll*x*x%P) if (t&1) res=1ll*res*x%P;
return res;
}
int main()
{
n=read(); P=read();
rep(i, 2, n<<1)
{
if (!b[i]) p[++tot]=i, b[i]=i;
for (int j=1; j<=tot && p[j]*i<=n<<1; j++)
{
b[p[j]*i]=p[j];
if (!(i%p[j])) break;
}
}
rep(i, 1, n) cnt[i]=-1;
rep(i, n+2, n<<1) cnt[i]=1;
per(i, n<<1, 2) if (b[i]<i)
cnt[b[i]]+=cnt[i], cnt[i/b[i]]+=cnt[i];
rep(i, 2, n<<1) if (b[i]==i) ans=1ll*ans*Pow(i, cnt[i])%P;
printf("%d
", ans);
return 0;
}
部分摘自百度百科：卡特兰数