组合数应用

卡特兰数

很多题的题解都是卡特兰数，但是要自己推出来

部分类型：

Transclude of 数学-2024-03-03-21.13.45.excalidraw

利用 $C_a^b=a!/(a-b)!b!$ 推出上述化简结果

则此题可以直接做

//质数用快速幂求逆元
LL qmi(LL a, LL k)
{
    LL ans = 1;
    while(k)
    {
        if(k & 1) ans = ans * a % m;
        a = a * a % m;
        k >>= 1;
    }
    return ans;
}
 
LL C(int a, int b)
{
    LL ans = 1;
    for(int i = a, j = 1; j <= b; i--, j ++)
    {
        ans = ans * i % m;
        ans = ans * qmi(j, m - 2) % m;
    }
    
    return ans;
}
 
int main()
{
    int n;
    cin >> n;
    
    LL ans = C(2 * n, n);
    cout << ans * qmi(n + 1, m - 2) % m << endl;
    
    return 0;
}