卡特兰数

• 定义
  卡特兰数非常常见，最为典型的就是给定n个1和n个0排列成为一个2n长度的01序列，要求对于任一个\(1\le k\le 2n\)都有从第一个数到第k个数中0的个数都不少于1的个数。
• 求法及其推导
  我们可以把这个01序列抽象成一个具体的问题:
  0代表向右走一步，1代表向上走一步，要求一共向右走n步向上走n步对于任一时刻向右走的步数都大于向上走的步数，最终到达(n,n)。
  我们不难发现y=x是一个分界点，如果走的路线全部都在y=x(图中绿线）的下方或者只是碰到y=x并未越过它则符合条件，当且仅当路线与y=x+1(图中红线)有交点不符合条件。
  
  设不符合条件的路径与红线的第一个交点为t，
  
  这里有一系列逻辑推导关系:\(一个路径是不合法路径\Longrightarrow 它与红线有一个交点t\Longrightarrow 这条路径t点之后的步数里向右走要比向上走多一步\Longrightarrow将t之后的路径沿着红线翻转后向上走要比向右走多两步\Longrightarrow 翻转后一定到达(n-1,n+1)点\),因为到达(n-1,n+1)点一定会穿过红线那么就有：所有非法路径的条数等于到(n-1,n+1)的条数。即为：\(C_{2n}^{n}-C_{2n}^{n-1}=\frac{(2n)!}{n!n!}-\frac{(2n)!}{(n-1)!(n+1)}=\frac{(2n)!(n+1)}{(n+1)!n!}-\frac{(2n)!n}{n!(n+1)!}=\frac{2n!}{(n+1)!n!}=\frac{1}{n+1}*\frac{2n!}{n!n!}=\frac{1}{n+1}C_{2n}^{n}\),所以卡特兰数为:\(\frac{C_{2n}^{n}}{n+1}\)
  -代码实现
  给定n个0和n个1，求卡特兰数，结果模上\(10{^9}+7\)

#include<iostream>

using namespace std;
typedef long long  LL;
const int N=2e5+10;
const int mod=1e9+7;
int fact[N],infact[N];
int qmi(int a,int b,int p)
{
    int res=1;
    while(b)
    {
        if(b&1)
        {
            res=(LL)res*a%p;
        }
        b>>=1;
        a=(LL)a*a%p;
    }
    return res;
}
int main()
{
    int n;
    cin>>n;
    int a=2*n,b=n;
    fact[0]=infact[0]=1;
    for(int i=1;i<=a;i++)
    {
        fact[i]=(LL)fact[i-1]*i%mod;
        infact[i]=(LL)infact[i-1]*qmi(i,mod-2,mod)%mod;
    }
    int res=(LL)fact[a]*infact[b]%mod*infact[b]%mod*qmi(n+1,mod-2,mod)%mod;
    printf("%d",res);
    return 0;
}