卡特兰数模板及其四个应用例题

在读题的时候,分析题意，假设数k为题上要求的某种状态，那么就可以把这段序列划分为两部分，比k大的部分（k+1到n）和比k小的部分（1到k-1），这两部分对应的情况种数分别是f(n-k)和f(k-1)。
而k可以从1取到n，所以把每种k的情况加起来就是答案。
答案形如这个样子
ans=f(0)f(n-1)+f(1)f(n-2)+f(2)f(n-3)+......+f(n-1)f(0)

如果遇到题目的思路是上面这样的，就是要用到卡特兰数。

1.进栈出栈
一段数的进出栈顺序的可能情况种数。
延展问题：排队找零。n个人手拿5元，n个人手拿10元，他们去排队买东西，东西价值5元，老板没有零钱（老板必须用收取的5元钞票给支付10元的顾客找零钱），请问一共有多少种排队方式？
将持5元者到达视作将5元入栈，持10元者到达视作使栈中某5元出栈，转化为进出栈问题。
2.凸多边形三角形划分
一个凸的n边形，用直线连接它的两个顶点使之分成多个三角形，每条直线不能相交，问一共多少种方案？
延展问题：圆划分。在圆上选2n个点，讲这些点成对连接起来，保证所有直线不相交，问一共多少种可能？
3.二叉树生成问题
有n个结点，请问总共能构成多少种不同的二叉树？
延展问题：满二叉树个数。n+1个叶子的满二叉树个数为多少？
4.阶梯问题
n个长方形填充一个高度为n的阶梯状图像方法数为多少？

 做题时，卡特兰数用到的公式并是上的那个，而是一个组合数:C(n,2*n)-C(n-1,2*n)。

1.数据范围a，b<=2000，时间复杂度O（n^2）
用杨辉三角即可；
2.数据范围x,y<=1e6,时间复杂度为O(n*logn)
用预处理加逆元即可；
3.当n和k<=1e18时，阶乘会超时
用卢卡斯。

1.数组要开数据最大值的两倍，因为组合数有2*n；
2.组合相加时要加mod，在取余mod，eg：（C(n,2*n)-C(n-1,2*n)+mod)%mod，因为取余后的数不存在相对大小，会出现负数。 

ll fact[2*maxn];//存阶乘，开2倍
ll infact[2*maxn];//存阶乘的逆元，开2倍

ll quick(ll a, ll b, ll p) {//快速幂
    ll res = 1;
    while (b > 0) {
        if (b & 1) res = res * a % p;
        b >>= 1;
        a = (a * a) % p;
    }
    return res;
}

ll C(ll k, ll n, ll p) {//求组合数的函数
    return n < k ? 0 : fact[n] * infact[k] % p * infact[n - k] % p;
}

ll lucas(ll k, ll n, ll p) {//卢卡斯函数（递归）
    return k == 0 ? 1 % p : lucas(k / p, n / p, p) * C(k % p, n % p, p) % p;
}

ll work(ll k, ll n, ll p) {//预处理数组，然后调用卢卡斯函数
    fact[0] = 1;
    infact[0] = 1;
    for (int i = 1; i <= n; i++) {
        fact[i] = fact[i - 1] * i % p;
        infact[i] = infact[i - 1] * quick(i, p - 2, p) % p;
    }
    return lucas(k, n, p);
}

int main() {
    ll n;
    cin >> n;
    ll p=1e9+7;
    cout<<(work(n, 2*n, p)-work(n-1, 2*n, p)+p)%p;//加p再取余
    return 0;
}