BISHI131　数楼梯¶

简单通过率 44.09%python3样例通过牛客 AC

一句话

每步走 1 或 2 阶，求走法数 mod 998244353。

解题思路¶

这题考什么¶

最入门的线性 DP。设 f_i 为走到第 i 阶的方案数，最后一步只能是从 i-1 迈 1 阶或从 i-2 迈 2 阶，两类方案互不重叠且覆盖全部情况：

f_i = f_{i-1} + f_{i-2},  f_1 = 1, f_2 = 2

也就是斐波那契数列（错开一位）。

数据规模与复杂度¶

n <= 1e5，O(n) 递推、O(1) 空间（滚动两个变量）。 n 只有 1e5，用不着矩阵快速幂。

坑在哪¶

n = 1 要特判（答案 1），否则 f_2 的初值会被误用；
每步都取模，不要先算大数最后再取模—— 虽然 Python 的大整数不会溢出，但 1e5 项的斐波那契有约 2 万位，大整数加法会退化成 O(位数)，总复杂度变成 O(n^2 / 64)，白白慢几十倍；
题目问的是「走到顶端」的方案数，f_n 就是答案，不用再加 1。

参考实现¶

solutions/BISHI131.py
import sys

MOD = 998244353


def main() -> None:
    n = int(sys.stdin.buffer.read().split()[0])
    if n == 1:                               # 递推从 f_2 起步，n = 1 落在起点之前，单独答
        sys.stdout.write("1\n")
        return
    a, b = 1, 2                              # f_1, f_2
    # 只保留相邻两项滚动向前，b 始终是当前算到的那一项；
    # 从 f_2 推到 f_n 需要 n - 2 步
    for _ in range(n - 2):
        a, b = b, (a + b) % MOD              # 每步取模，避免大整数退化
    sys.stdout.write("%d\n" % b)


main()

BISHI131 数楼梯¶