[NOIP2003-普及] 栈

题目描述

给定 $n$ （ $1\le n\le 18$ ），初始有操作数序列 $1,2,\dots,n$ 、空栈和空输出序列。每次可将操作数序列头端元素入栈，或将栈顶元素弹出到输出序列末尾。求最终能得到的不同输出序列总数。

样例 $n=3$ 时输出为 $5$ 。

思路

合法输出序列的总数即为第 $n$ 个卡特兰数。利用递推式 $C_0=1$ ， $C_k=C_{k-1}\cdot\dfrac{2(2k-1)}{k+1}$ ， $O(n)$ 递推即可得到答案。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 05:05
# update_at: 2026-10-02 05:05

import sys


def catalan(n: int) -> int:
    """第 n 个卡特兰数：C_k = C_{k-1} * 2(2k-1) / (k+1)，整除在乘法之后做。"""
    count = 1  # C_0 = 1：空序列只有一种"什么都不做"的方案
    for k in range(2, n + 1):
        count = count * 2 * (2 * k - 1) // (k + 1)
    return count


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)  # 题面只给一个整数 n
    print(catalan(n))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-04 14:46
 * update_at: 2026-10-04 14:46
 */
#include <iostream>
using namespace std;

typedef long long ll;

// 第 n 个卡特兰数：C_0=1, C_k = C_{k-1} * 2(2k-1) / (k+1)，整除在乘法之后做。
ll catalan(int n) {
    ll res = 1; // C_0 = 1
    for (int k = 2; k <= n; ++k)
        res = res * 2 * (2 * k - 1) / (k + 1);
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    cout << catalan(n) << "\n";
    return 0;
}

目录

题目描述

思路

参考代码