python/TangDou/CSP-J/AcWingTraining/T6/415.md

AcWing 415. 栈

(组合计数,卡特兰数) O(n^2)

首先任何一种合法的入栈、出栈操作序列都可以得到一个不同的$1$~$n$的排列，因此可以得到的排列总数等于合法入栈、出栈操作序列的个数。

将入栈操作记作$0$，出栈操作记作$1$，那么任意一个合法的入栈、出栈操作序列都和AcWing 889. 满足条件的$01$序列中定义的合法$01$序列一一对应，因此本题的答案和上一题相同，都是第$n$个卡特兰数。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 40;
LL c[N][N];

//1、组合数公式的理解
//https://www.cnblogs.com/littlehb/p/15010406.html

//2、卡特兰数
// https://www.bilibili.com/video/BV1wr4y1q7qw
// https://www.bilibili.com/video/BV1tE411R7mw

int main() {
    // 预处理组合数
    for (int i = 0; i < N; i++)
        for (int j = 0; j <= i; j++)
            if (!j)
                c[i][j] = 1;
            else
                c[i][j] = c[i - 1][j - 1] + c[i - 1][j];

    int n;
    cin >> n;
    // 卡特兰数
    cout << c[n * 2][n] / (n + 1) << endl;
    return 0;
}