卡特兰数 | 流云鹤

分析

将卡特兰数记为。它的含义是在平面直角坐标系中从出发，每次只能向右走或者向上走，且不能超过这条线，走到的不同路径数量，它有三种计算公式：

这个思路就是先求路径总数，在次移动中选择 n 次右移即。再求越过对角线的路径数，可以发现只要越过对角线必然会碰到，我们假设这条非法路径与的第一个交点为，我们将该点之后的点都关于对称过去，这样终点就会变为。所以说每条非法路径都可以映射到从到的路径，所以非法路径数就是。那么合法路径数 (卡特兰数) 就是。
在运用这个公式时需要注意到模运算后计算减法可能为负数，应加模数再取模。
将 1) 式展开化简得：
这个可以利用 2 式来证明，即证明

$$
\frac{1}{n+1}\frac{(2n)!}{n!\ n!}=\frac{4n-2}{n+1}\frac{1}{n}\frac{(2n-2)!}{(n-1)!(n-1)!}

\frac{(2n)(2n-1)}{n}=(4n-2)

(2n)*(2n-1)=(4n-2)*n=4n^2-2n
$$
可以得证。
所以当一个题目中有两种操作，一种操作的数量不能超过另一种操作的数量时，这些操作的合法方案数，通常是卡特兰数。

常见应用

括号序列计数问题

由 n 对左右括号构成的合法的括号序列数。
同样的可以类比坐标系问题，和要求不能超过一样，这里要求在任意一个前缀中，左括号的数量不少于右括号的数量。
这样就可以把左括号映射为向右走，右括号映射为向左走。
一组合法的括号序列即为合法的路径。

01 字串问题

一组有 n 个 0 和 n 个 1 组成的字串，要求所有的前缀字串中都满足 1 的个数不超过 0 的个数。求这样的字串数。

出栈序列计数问题

一个栈（无穷大）的进栈序列为有多少个不同的出栈顺序？
这里将入栈看作左括号，出栈看作右括号，这样合法方案数量也为卡特兰数。

二叉树计数问题

n 个结点可以构造多少个不同的二叉树。
不懂但硬记。

圆内不相交弦计数问题

圆上有 2𝑛个点，将这些点成对连接起来且使得所得到的 𝑛 条线段两两不交的方案数。

三角剖分计数问题

通过连接节点将边的凸多边形划分成 n 个三角形方法数。

球迷购票问题

题目链接：
P1754 球迷购票问题 - 洛谷
思路：
要求不出现找不出钱的情况，那么就需要队列前缀中拿100 的人数不超过拿 50 的人数。这样将 100 看作右括号，50 看作左括号。
数据不大，可以用递推式。
代码：

void solve()
{
    int n;
    cin>>n;
    int ans=1;
    for(int i=1;i<=n;i++)
    {
        ans=ans*(4*i-2)/(i+1);
    }
    cout<<ans;
}

思路： 当然这个题目也可以用 dp 来解。
令 dp[i][j] 表示前 i 个人有 j 张 50。那么状态转移公式就是：
$第个人拿$
$第个人拿$
代码：

const int N=55;
int dp[N][N];
void solve()
{
    int n;
    cin>>n;
    dp[0][0]=1;
    for(int i=1;i<=2*n;i++)
    {
        for(int j=0;j<=n&&j<=i;j++)
        {
            if(j-1>=0)dp[i][j]+=dp[i-1][j-1];
            if(i+1>=j+1)dp[i][j]+=dp[i-1][j+1];
        }
    }
    cout<<dp[2*n][0];
}

White and Black Balls

题目链接：
E - White and Black Balls
思路：
和推导卡特兰数类似。
代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
const int N=2e6+5;
int fact[N],infact[N];
const int MOD=1e9+7;
int qmi(int a,int b,int p)
{
    int res=1;
    while(b){
        if(b&1)res=res*a%p;
        b>>=1;
        a=a*a%p;
    }
    return res;
}
void init()
{
    fact[0]=infact[0]=1;
    for(int i=1;i<=N;i++)
    {
        fact[i]=fact[i-1]*i%MOD;
        infact[i]=infact[i-1]*qmi(i,MOD-2,MOD)%MOD;
    }
}
int C(int a,int b){
    if(b>a||b<0)return 0;
    return fact[a]*infact[b]%MOD*infact[a-b]%MOD;
}
void solve()
{
    int n,m,k;
    cin>>n>>m>>k;
    if(n>m+k){
        cout<<"0"<<endl;
        return;
    }
    int ans=(C(n+m,m)-C(n+m,m+k+1)+MOD)%MOD;
    cout<<ans;
}
signed main(){
	IOS
	//int t;
	//cin>>t;
    init();
	int t=1;
	while(t--)
	{
		solve();
	}
}