$\Huge\color{orchid}{点击此处获取更多干货}$

卡特兰数

卡特兰数是在一系列计数问题中频繁出现的一条序列$c=\{1,1,2,5,14,42,132,429,1430,4862,…\}$。该序列的通项公式为$c(n)=C_{2*n}^{n}/(n+1)$，其中$n$的取值范围为所有自然数。应用场景和数学理论都可以推导出这个公式，本帖重点在应用场景中的推导。

卡特兰数在考研数据结构中有一个很经典的问题：将一些元素按照某种顺序入栈，并允许入栈和出栈两种操作交错，可以得到的出栈顺序有几种？
对于该问题中的所有元素，假设其数量为$n$，那么将其全部入栈再出栈，就对应了有$2*n$个操作（$n$次入栈和$n$次出栈）。由于入栈元素顺序已经固定，因此只需要在$2*n$个位置中选择$n$个作为“入栈”即可，总数为$C_{2*n}^n$。但是，要产生合理的出栈顺序，必须满足以下条件：
1. 所有操作执行完之后，栈内必须不含任何元素，即“入栈”操作不能连续的出现在最后；
2. 一个元素只有“入栈”了才能有后续“出栈”行为，即操作序列的任意前缀中，“入栈”操作的数量不能少于“出栈”操作的数量。

不满足以上条件的，均为不合法序列，它们的共同特点为：必然存在某一个奇数位序$2*m+1$，在以该位置为端点的前缀中，包含$(m+1)$次出栈操作和$m$次入栈操作，而其余部分则正好相反，入栈操作比出栈操作多1。将剩余部分的操作取反，即“入栈”视为“出栈”，“出栈”视为“入栈”，则整个序列中，就包含了$(n+1)$次出栈和$(n-1)$次入栈，因此任意一种不合法序列都对应了某一种含有了$(n+1)$次出栈和$(n-1)$次入栈的序列，这些共有$C_{2*n}^{n+1}$种。从总数中减去不合法数量，就是结果。结合组合数的公式，它可以改写为$C_{2*n}^{n}/(n+1)$，即第$n$个卡特兰数$c(n)$

对于该问题中的0和1，分别将其视作“入栈”和“出栈”即可。考虑到取模需求，除$(n+1)$可以改为乘$(n+1)$的逆元，下面是完整代码，组合数求解的各种方法已经前述备至，故不在注释中额外解释了

C++ 代码

#include <iostream>
using namespace std;
const size_t MOD = 1e9 + 7;

size_t quickPower(size_t base, size_t power, size_t mod) {
    size_t ans = 1;
    while (power > 0) {
        if (power & 1) ans = (ans * base) % mod;
        base = (base * base) % mod;
        power >>= 1;
    }
    return ans;
}

size_t combine(size_t n, size_t m, size_t p) {
    size_t ans = 1;
    while (m > 0) {
        ans = (ans * (n + 1 - m)) % p;
        ans = (ans * quickPower(m, p - 2, p)) % p;
        m--;
    }
    return ans;
}

size_t catalanNum(size_t n, size_t p) {
    size_t cb = combine(2 * n, n, p);
    return (cb * quickPower(n + 1, p - 2, p)) % p;
}

int main() {
    int n;
    cin >> n;
    cout << catalanNum(n, MOD) << endl;
    return 0;
}