卡特兰数

概述

卡特兰数是一种经典的组合数，经常出现在各种计算中，其前几项为 : 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845…

---

常见公式

• \(H_n=\begin{cases} \sum_{i = 1}^nH_{i - 1}H_{n-i},(n\ge2, n\in N_{+})\\ 1,(n=0,1) \end{cases}\)
•  \(H_n = \frac{H_{n-1}(4n-2)}{n+1}\)
•  \(H_n=C_{2n}^n-C_{2n}^{n-1}=\frac{C_{2n}^n}{n+1}\)

---

例1 P1641 [SCOI2010]生成字符串

题目描述

lxhgww 最近接到了一个生成字符串的任务，任务需要他把 n 个 1 和 m 个 0 组成字符串，但是任务还要求在组成的字符串中，在任意的前 k 个字符中，1 的个数不能少于 0 的个数。现在 lxhgww 想要知道满足要求的字符串共有多少个，聪明的程序员们，你们能帮助他吗？

输入格式

输入数据只有一行，包括 2 个数字 n 和 m。

输出格式

输出数据是一行，包括 1 个数字，表示满足要求的字符串数目，这个数可能会很大，只需输出这个数除以 20100403 的余数

输入样例

2 2

输出样例

2

题解

将1和0的操作转换到坐标系中，假设有1则\((x+1，y+1)\)，有0则\((x+1,y-1)\)，我们发现终点为\((n+m,n-m)\)，若存在前k字母中0个数大于1，则在坐标系中曲线经过\(y=-1\)，将终点关于\(y=-1\)对称，则终点对称点为\((n+m，m-n-2)\)，于是就有\(n-m+1\)步的向上变成向下，即一共有\(n+1\)步向下，所有情况有\(C_{c+m}^n\)种可能，不合法的有\(C_{n+m}^{m-1}\)或\(C_{n+m}^{n+1}\)种可能，答案相减即可，另一种对称方法是将起点关于\(y=-1\)对称，则起点变为\((0，-2)\)，到达\((n+m，n-m)\),需要将一步向下变为向上，则不合法有\(C_{n+m}^{m-1}\)种可能

代码

#include<bits/stdc++.h>  
#define int long long  
using namespace std;  
const int mod=20100403;  
int qpow(int a,int n,int mod)  
{  
    int res=1;  
    while(n)  
    {  
        if(n&1) res=res*a%mod;  
        a=a*a%mod;  
        n>>=1;  
    }  
    return res;  
}  
int C(int a,int b,int mod)  
{  
    int res=1;  
    for(int i=1,j=a;i<=b;i++,j--)  
    {  
        res*=j;  
        res%=mod;  
        res*=qpow(i,mod-2,mod);  
        res%=mod;  
    }  
    return res;  
}  
signed main()  
{  
    int n,m;  
    cin>>n>>m;  
    cout<<((C(n+m,m,mod)-C(n+m,m-1,mod))%mod+mod)%mod<<endl;  
    return 0;  
}