卡特兰数（竞赛用板子）

闲谈
卡特兰数是组合数学方面的知识，在程序设计竞赛上也有考查，并且很多问题都涉及到卡特兰数。
第一次接触卡特兰数是在昨晚，是在gym上做吉林省赛的时候碰到的，吉林省赛的K题，有k种括号，问n个括号匹配的方案数有多少，答案对1e9+7求余。刚拿到这个题发现k种括号其实没用，只需要算出一种括号有n个的匹配数目有多少然后把结果乘上k^n不就行了？分析完之后发现，一种括号有n个的匹配数目有多少不会算……推导了俩小时还是找不出来公式，无奈之下上csdn搜索括号匹配方案数，然后就接触到了卡特兰数这个组合数学的知识，感觉还是挺神奇的，反正让我推导的话别说俩小时了，两年都不一定能推出来……

描述
简单地用几何意义来描述一下卡特兰数。在一个二维平面上，从原点(0,0)出发，到点(n,n)，其中每一步只能向右走或者向上走，并且在移动的过程中不能越过y=x这条直线的方案总数。例如，从(0,0)到(1,1)，只能先向右后向上，只有一种方案，f[1] = 1；从(0,0)到(2,2)，可以右上右上，也可以右右上上，有两种方案，f[2] = 2。f[n]代表从(0,0)到(n,n)的方案总数，也对应着卡特兰数数列的第n项。

公式
呃，推导我不会啊，直接上公式吧。
有两个很常见的公式，f[n] = C(2n, n) - C(2n, n + 1)，f[n] = 1 / (n + 1) * C(2n, n)，其中第二个公式是由第一个公式推导得来的。但是用计算机算组合的话实现还好，但是时间复杂度略高，数据给大了容易T。
还有一个公式，f[n] = f[n - 1] * (4 * n - 2) / (n + 1)，用这个公式处理起来就快很多，但是会涉及到除法求余，要用到费马小定理。

应用
在程序设计竞赛中，卡特兰数可以解决以下问题：
1.进出栈方案个数问题
2.二叉树方案个数问题
5.凸多边形三角划分问题
6.括号匹配方案个数问题

例题
就用最开始提到的吉林省赛K题吧，感觉这题还不错。
Bracket Sequence

#include 
using namespace std;
#define N 100005
#define MOD 1000000007
long long f[N];
long long ex_mod(long long x)
{
    long long res = 1;
    long long y = MOD - 2;
    while(y)
    {
        if(y & 1) res = (res * x) % MOD;
        x = (x * x) % MOD;
        y >>= 1;
    }
    return res;
}
void init(int n)
{
    f[0] = 1;
    for(int i = 1; i <= n; i++)
        f[i] = (f[i - 1] * (((4 * i - 2) * ex_mod(i + 1)) % MOD)) % MOD;
}
int main()
{
    init(100000);
    int n, k;
    cin >> n >> k;
    long long mul = 1;
    for(int i = 1; i <= n; i++) mul = (mul * k) % MOD;
    cout << (f[n] * mul) % MOD << endl;
    return 0;
}

应该没啥要解释的吧，卡特兰数板子题。
那么本篇博客到这里也就结束了，话说好久没写博客了，都不会发博客了，刚才在写博客之前发现上次写的博客竟然没发，我记得我发了啊……在草稿箱里存了半个月（喷血.jpg）。