卡特兰数

卡特兰数的几何意义

简单来说，卡特兰数就是一个有规律的数列，在坐标图中可以表示为：从原点(0,0)出发，每次向x轴或者y轴正方向移动1个单位，直到到达(n,n)点，且在移动过程中不越过第一象限平分线的移动方案总数。

模板题:https://www.acwing.com/activity/content/problem/content/959/
代码：

#include<bits/stdc++.h>
using namespace std;
const int p =1e9+7;
const int N =200005;
int fact[N];
int qkm(int a,int b)
{
    int res =1;
    while(b)
    {
        if(b&1) res =(long long)res*a%p;
        //cout<<res<<endl;
        b>>=1;
        a=(long long)a*a%p;
    }
    return res;
}
void init()
{
    fact[1]=1;
    for(int i=2;i<=N;i++)
    {
        fact[i] = (long long)fact[i-1]*i%p;
        //cout<<fact[i]<<endl;
    }
}

int main(void)
{
    int n;
    cin>>n;
    int a = 2*n;
    int b = n;
    init();
    int ans = (long long)fact[a]*qkm(fact[a-b],p-2)%p;
    ans = (long long)ans*qkm(fact[b],p-2)%p;
    // cout<<ans<<endl;
    cout<<(ans/(n+1))%p<<endl;
}