博客

卡特兰数就结论来说是指从1到n所有数经过入栈和出栈后得到的排列的种类数，值为 C(2n,n)/(n+1)

原理：将其转换为从(0,0)点到(n,n)点的路径数中不越过 y=x 线的路径数，用所有的路径数减去非法路径数，

每条非法路径都会经过y=x+1这条线，将其经过 y=x+1 这条线后的路径对这条线作对称，

发现它的终点会落在点(n-1,n+1)上，每条非法路径都能通过这样的变化转为以(n-1,n+1)为终点的一条路径，反过来，每一条以(n-1,n+1)为终点的路径也能转化为一条以(n,n)为终点的非法路径，所以非法路径数就是从原点到(n-1,n+1)的路径数，即

所以最终结果就是总路径数

减去非法路径数

化简得到

。

组合数实现：

long long c[N][N];
long long C(int x,int y)
{
    if(c[x][y]!=-1)return c[x][y];
    if(y>x)return c[x][y]=0;
    if(y==0)return c[x][y]=1;
    if(x==y)return c[x][y]=1;
    return c[x][y]=C(x-1,y-1)+C(x-1,y);
}

数据较大时使用

实现，注意除法使用逆元

const int N = 1e5+10;
const int Mod = 1e9+7;
int jc[N], fjc[N];

int gmi(int a, int b = Mod - 2)      //逆元(快速幂模板)
{
    if (a == 0 || a == 1)
        return a;
    int res = 1, t = a;
    while (b)
    {
        if (b & 1)
            res = res * t % Mod;
        b >>= 1;
        t = t * t % Mod;
    }
    return res;
}
inline int C(int x, int y)
{
    if(x < y)return 0;
    return jc[x] * fjc[x - y] % Mod * fjc[y] % Mod;
}
void init()
{
    jc[0] = 1;
    for (int i = 1; i < N; i++)
        jc[i] = i * jc[i - 1] % Mod;
    fjc[N - 1] = gmi(jc[N - 1]);
    for (int i = N - 1; i >= 0; i--)
        fjc[i] = fjc[i + 1] * (i + 1) % Mod;
}