「一本通 6.6 练习 11」树屋阶梯

GitHub跳转原题关系图返回列表

阶梯切割方案数是卡特兰数 C(2n,n)/(n+1)：以最后一刀位置递归拆解，得到卡特兰递推，用 math.comb 精确大整数一次算出。

OJ: roj

题目 ID: 1662

难度:提高+/省选-

标签:组合数学卡特兰数递推

创建: 2026-10-01 01:05

更新: 2026-10-07 13:50

目录

  1. 形式化题目
  2. 正解
    1. 思路
      1. 代码
      2. 复杂度
    2. 总结

    形式化题目

    用 NN 个 1×11 \times 1 尺的空心方钢拼出高度、宽度各 NN 尺的阶梯（每阶高宽均为 1 尺），钢材可任意切割拼接但空心面不能朝上。求拼法总数。

    正解

    思路

    1. 建模为阶梯切割

    「钢材空心面不能向上」等价于把一个 nn 阶阶梯（轮廓为 1+2+⋯+n1+2+\cdots+n 的直角三角形）用矩形拼满，且每个矩形内部不能有"凹形"缺口。经典结论：这等价于对阶梯做递归二分割，方案数满足卡特兰递推。

    2. 卡特兰递推的来源

    考虑包含阶梯最右下角那个 1×11 \times 1 方格的矩形。它必然切出一个横跨某一层的"断层"，把剩余部分分成一个同构的小阶梯问题：

    f(n)=∑k=0n−1f(k)⋅f(n−1−k),f(0)=1f(n) = \sum_{k=0}^{n-1} f(k) \cdot f(n-1-k), \quad f(0) = 1

    这正是卡特兰数的标准递推，闭式为：

    f(n)=1n+1(2nn)=(2nn)−(2nn−1)f(n) = \frac{1}{n+1}\binom{2n}{n} = \binom{2n}{n} - \binom{2n}{n-1}

    3. 精确计算

    n≤500n \le 500 时 C500C_{500} 约有 297 位十进制数字，必须用高精度。Python 的任意精度整数与 math.comb（精确二项式系数）让实现只需一行：

    python
    print(comb(2 * n, n) // (n + 1))

    先整除后输出，comb 返回精确值，除法可整除，无浮点误差。

    代码

    Python 版：

    python
    #!/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-01 01:10
# update_at: 2026-10-01 01:10

import sys
from math import comb


def solve() -> None:
    n = next(iter(map(int, sys.stdin.buffer.read().split())))

    # 方案数就是第 n 个卡特兰数 C(2n,n)/(n+1)；math.comb 是精确大整数运算，
    # 先整除再输出，n <= 500 时结果有 297 位也不会溢出。
    print(comb(2 * n, n) // (n + 1))


if __name__ == "__main__":
    solve()

    C++ 版（同一算法）：

    cpp
    /**
 * 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-01 00:46
 * update_at: 2026-10-06 01:18
 */
#include <cstdio>
typedef long long ll;

// 阶乘规模 n<=500，第 n 个卡特兰数约 300 位十进制，用大整数手写高精度。
const ll BASE = 1000000000; // 大整数每段存 9 位十进制，方便输出
ll dig[1005];               // dig[0] 是最低位，dig[len-1] 是最高位
ll n;
int len;                    // 当前大整数的段数

// 大整数乘一个小整数 b
void big_mul(ll b) {
    ll carry = 0;
    for (int i = 0; i < len; i++) {
        ll cur = dig[i] * b + carry;
        dig[i] = cur % BASE;
        carry = cur / BASE;
    }
    while (carry > 0) {
        dig[len] = carry % BASE;
        carry /= BASE;
        len++;
    }
}

// 大整数除以一个小整数 b（保证能整除）
void big_div(ll b) {
    ll rem = 0; // 从高位向低位做竖式除法时的余数
    for (int i = len - 1; i >= 0; i--) {
        ll cur = rem * BASE + dig[i];
        dig[i] = cur / b;
        rem = cur % b;
    }
    while (len > 1 && dig[len - 1] == 0) {
        len--;
    }
}

// 按 10^9 进制逐段输出，除最高段外每段补足 9 位
void big_print() {
    printf("%lld", dig[len - 1]);
    for (int i = len - 2; i >= 0; i--) {
        printf("%09lld", dig[i]);
    }
    printf("\n");
}

int main() {
    scanf("%lld", &n);

    // 卡特兰数递推：C_{k+1} = C_k * 2*(2k+1) / (k+2)，起点 C_0 = 1
    dig[0] = 1;
    len = 1;
    for (ll k = 0; k < n; k++) {
        big_mul(2 * (2 * k + 1));
        big_div(k + 2);
    }
    big_print();

    return 0;
}

    复杂度

    • 时间复杂度：math.comb 内部为 O(n)O(n) 次大整数乘除量级（Karatsuba 之下更快），对 n=500n = 500 瞬时完成。
    • 空间复杂度：O(nlog⁡n)O(n \log n) 位，存储 C2nnC_{2n}^n 的中间大整数。

    总结

    • 「拼阶梯」问题的组合结构是卡特兰数：按包含角落的矩形切分得到标准递推 f(n)=∑f(k)f(n−1−k)f(n) = \sum f(k)f(n-1-k)。
    • 大数方案数直接交给 Python 任意精度整数 + math.comb，无需手写高精度。
    • 与 Catalan 圆括号、凸多边形三角剖分、出栈序列同源，识别出卡特兰模型即可秒杀。