散步

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

把路径唯一拆成若干段「远足」,每段长 2j 的方案数是 2·Catalan(j-1),于是答案满足 50 阶常系数线性递推,用伴随矩阵快速幂在 O(m³log n) 内求出。

OJ: roj

题目 ID: 1795

难度:提高+/省选-

标签:数学矩阵快速幂线性递推卡特兰数python

创建: 2026-10-08 03:35

更新: 2026-10-08 03:35

形式化题目

在数轴上的整数点做随机游走:时刻 00 位于原点 00,每个单位时间移动 +1+1 或 −1-1, 在时刻 nn 必须回到原点 00。此外还有一条持续性约束:任何一次离家的持续时长不超过 mm, 即若在时刻 t1t_1 离开原点、在时刻 t2t_2 首次重新回到原点,则必须有 t2−t1⩽mt_2 - t_1 \leqslant m。

求满足条件的走法条数,对 109+710^9+7 取模。两条走法不同当且仅当存在某个单位时刻选择的 方向不同。

数据范围:2⩽n⩽1092 \leqslant n \leqslant 10^9,2⩽m⩽1002 \leqslant m \leqslant 100,保证 nn、mm 均为偶数。

正解

思路

朴素做法。 直接按题面定义 DP:状态记「当前位置 pp 与本次离家已经走了 ss 步」, s=0s = 0 表示此刻在家。每步从 (p,s)(p, s) 转移到 (p±1,s+1)(p \pm 1, s+1); 如果 p±1=0p \pm 1 = 0,就要求 s+1⩽ms + 1 \leqslant m(这段离家结束了)。跑满 nn 步, 答案是终态「在家」的方案数。状态数是 O(n⋅m)O(n \cdot m),时间 O(n⋅m)O(n \cdot m)—— nn 到 10910^9 时完全不可行。

瓶颈在哪? 状态里同时带着「在哪里」和「出门多久」,两个维度都被 nn 撑大了。 但回到原点这个条件非常强:路径必经 00,而 00 正是把整条路径切成互不干扰小段的 天然分界点。所以不必逐时刻推。

关键观察一:路径唯一分解成「远足」。 每当路径回到 00,就切一刀。这样一条合法路径 被唯一拆成若干段 E1,E2,…,ErE_1, E_2, \dots, E_r,每段满足:起点与终点都在 00, 中间时刻坐标严格非 00。称这样一段为一次远足;段长只能是偶数 2j2j, 且约束就是 2j⩽m2j \leqslant m,即 j⩽d:=m/2j \leqslant d := m/2。于是

答案=∑k1+⋯+kr=N1⩽ki⩽d∏i=1raki,N=n2,\text{答案} = \sum_{\substack{k_1 + \cdots + k_r = N \\ 1 \leqslant k_i \leqslant d}} \prod_{i=1}^{r} a_{k_i}, \qquad N = \frac{n}{2},

其中 aja_j 是长为 2j2j 的远足条数。

关键观察二:aj=2 Cj−1a_j = 2\,C_{j-1}。 一次远足要么整段在正半轴(首步 +1+1、末步 −1-1), 要么整段在负半轴,两者由整体取负一一对应,条数相同。看正半轴的那种:去掉首尾两步, 剩下 2j−22j - 2 步从 11 出发、中途坐标始终 ⩾1\geqslant 1、最后回到 11。 把坐标整体下移 11,就变成长度为 2j−22j-2、始终 ⩾0\geqslant 0 的闭路径,这正是 Dyck 路径, 条数是第 j−1j-1 项卡特兰数 Cj−1C_{j-1}。所以

aj=2 Cj−1=2⋅1j(2j−2j−1)(mod109+7).a_j = 2\,C_{j-1} = 2 \cdot \frac{1}{j}\binom{2j-2}{j-1} \pmod{10^9+7}.

用 Ci=4i−2i+1Ci−1C_i = \frac{4i-2}{i+1}C_{i-1}(或阶乘 + 逆元)只需 O(d)O(d) 就能全部算出。

关键观察三:ff 满足常系数线性递推。 设 f(t)f(t) 为「恰好走 2t2t 步、回到 00 且合法的 方案数」。按最后一段远足分类(它前面的部分仍是同型的合法路径):

f(0)=1,f(t)=∑j=1min⁡(t, d)aj f(t−j)(t⩾1).f(0) = 1, \qquad f(t) = \sum_{j=1}^{\min(t,\,d)} a_j \, f(t - j) \quad (t \geqslant 1).

答案是 f(N)f(N)。这是阶数为 dd 的常系数齐次线性递推,而 d=m/2⩽50d = m/2 \leqslant 50 很小、 N=n/2⩽5×108N = n/2 \leqslant 5 \times 10^8 很大——标准的伴随矩阵快速幂场景。

转移矩阵。 取状态向量

F(t)=[ f(t),  f(t−1),  …,  f(t−d+1) ]T,F(t) = \bigl[\,f(t),\; f(t-1),\; \dots,\; f(t-d+1)\,\bigr]^{\mathsf T},

构造 d×dd \times d 矩阵 AA:第一行是 [a1,a2,…,ad][a_1, a_2, \dots, a_d],次对角线(第 ii 行第 i−1i-1 列, i⩾2i \geqslant 2)为 11,其余为 00。则 F(t)=A F(t−1)F(t) = A\,F(t-1)。

初始状态取 F(0)=[1,0,…,0]TF(0) = [1, 0, \dots, 0]^{\mathsf T}——因为 f(0)=1f(0) = 1,而 f(−1),f(−2),…f(-1), f(-2), \dots 这些「负步数」项按 00 补。如此 F(N)=ANF(0)F(N) = A^N F(0),而 F(0)F(0) 只有第一个分量非零, 所以所求 f(N)f(N) 恰好就是 (AN)0,0(A^N)_{0,0},连初始向量都不必单独乘。

以样例 n=10, m=6n = 10,\, m = 6 验证:d=3d = 3,a1=2C0=2a_1 = 2C_0 = 2,a2=2C1=2a_2 = 2C_1 = 2,a3=2C2=4a_3 = 2C_2 = 4, f(t)=2f(t−1)+2f(t−2)+4f(t−3)f(t) = 2f(t-1) + 2f(t-2) + 4f(t-3),算得 f(0..5)=1,2,6,20,60,184f(0..5) = 1, 2, 6, 20, 60, 184,f(5)=184f(5) = 184, 与样例相符。

数据说明。 本题素材来自信息学奥赛一本通《高手训练篇》,其 data/ 目录附带 生成脚本 data.py,即测试数据是按题面自造的,出题意图与官方原题可能存在偏差。 本解已直接用该 data/ 的 10 个 .in 点逐点核对 .out,全部一致。

代码

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-08 03:35
# update_at: 2026-10-08 03:35

import sys

MOD = 10 ** 9 + 7

type Vec = list[int]      # 一个长度为 d 的模 MOD 向量
type Mat = list[Vec]      # d x d 的模 MOD 矩阵(行优先)


def mat_mul(x: Mat, y: Mat) -> Mat:
    """矩阵乘法:恒等式 z[i][j] = sum_k x[i][k]*y[k][j] mod MOD,内层用 zip 转置求和。"""
    yt = list(zip(*y))                              # 转置后每列变成一行,便于与 x 的行做点积
    return [[sum(a * b for a, b in zip(row, col)) % MOD for col in yt] for row in x]


def mat_pow_elem(base: Mat, e: int) -> int:
    """伴随矩阵快速幂,返回 (base^e)[0][0] —— 即递推第 e 项 h(e)。"""
    d = len(base)                                   # 阶数由矩阵边长给出,无需另传参
    r = [[1 if i == j else 0 for j in range(d)] for i in range(d)]  # 单位矩阵
    while e:
        if e & 1:
            r = mat_mul(r, base)
        base = mat_mul(base, base)
        e >>= 1
    return r[0][0]


def catalan_times_two(d: int) -> Vec:
    """coef[j] = 2 * Catalan(j) = 长为 2(j+1) 的远足方案数,j 取 0..d-1。"""
    fact = [1] * (2 * d + 1)                        # 阶乘表,(2d)! 以内够用
    for i in range(1, 2 * d + 1):
        fact[i] = fact[i - 1] * i % MOD
    inv_fact = [1] * (2 * d + 1)
    inv_fact[2 * d] = pow(fact[2 * d], MOD - 2, MOD)
    for i in range(2 * d, 0, -1):
        inv_fact[i - 1] = inv_fact[i] * i % MOD
    return [2 * fact[2 * j] * inv_fact[j] % MOD * inv_fact[j + 1] % MOD for j in range(d)]


def companion_matrix(d: int) -> Mat:
    """h(t) = sum_j c_j h(t-j) 的伴随矩阵:第一行放系数,次对角线为 1。"""
    a: Mat = [[0] * d for _ in range(d)]
    a[0] = catalan_times_two(d)
    for i in range(1, d):
        a[i][i - 1] = 1                             # 把 f(t-1..t-d+1) 右移一格
    return a


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)                   # 题面的 n、m,均为偶数
    d = m // 2                                      # 递推阶数 d = m/2

    # 初始状态 [h(0), h(-1), ...] = [1, 0, ...],所以 (A^t)[0][0] 就是 h(t)
    matrix = companion_matrix(d)
    print(mat_pow_elem(matrix, n // 2))


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-08 03:35
 * update_at: 2026-10-08 03:35
 */
// 一本通 1795《散步》:数轴上从 0 出发,n 步每步 ±1,每段离家的连续时间 <= m,
// 第 n 步恰好回到家,求方案数 mod 1e9+7。2<=n<=1e9,2<=m<=100,n、m 均为偶数。
//
// 把「每次回家」当作一次分界,整条路径唯一拆成若干段「远足」(起点终点为 0、
// 中途坐标不为 0)。长为 2j 的远足数 = 2*Catalan(j-1):首步 ±1 定符号,
// 中间 2j-2 步是平移后的非负走法。
// 记 h(t) = 走 2t 步恰好回家的合法方案数,d = m/2,则
//     h(0) = 1,  h(t) = sum_{j=1..d} c_j * h(t-j),  c_j = 2*Catalan(j-1)。
// 这是 d (<=50) 阶常系数线性递推,用伴随矩阵快速幂求第 N = n/2 项。

#include <cstdio>
#include <cstring>

typedef long long ll;

const ll MOD = 1000000007LL;
const int MAXD = 55;   // m <= 100 时阶数 d = m/2 <= 50,留一点余量

int d;                 // 递推阶数 d = m/2
ll coef[MAXD];         // coef[j] = 长为 2(j+1) 的远足方案数 = 2*Catalan(j)
ll fact[2 * MAXD + 5];      // 阶乘表,最大用到 (2d)!
ll inv_fact[2 * MAXD + 5];  // 阶乘的逆元表,配合费马小定理求组合数

struct Mat {
    ll a[MAXD][MAXD];
    Mat() { memset(a, 0, sizeof(a)); }
};

// 矩阵乘法,全部 64 位并即时取模,避免中间乘积溢出
Mat mul(const Mat &x, const Mat &y) {
    Mat r;
    for (int i = 0; i < d; i++) {
        for (int k = 0; k < d; k++) {
            if (x.a[i][k] == 0) continue;      // 稀疏时直接跳过,省一半常数
            ll v = x.a[i][k];
            for (int j = 0; j < d; j++) {
                r.a[i][j] = (r.a[i][j] + v * y.a[k][j]) % MOD;
            }
        }
    }
    return r;
}

Mat mpow(Mat base, ll e) {
    Mat r;
    for (int i = 0; i < d; i++) r.a[i][i] = 1;  // 单位矩阵
    while (e > 0) {
        if (e & 1) r = mul(r, base);
        base = mul(base, base);
        e >>= 1;
    }
    return r;
}

ll qpow(ll a, ll b) {
    ll r = 1;
    a %= MOD;
    while (b > 0) {
        if (b & 1) r = r * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return r;
}

int main() {
    ll n, m;
    if (scanf("%lld %lld", &n, &m) != 2) return 0;
    d = m / 2;                     // m <= 100,故 d <= 50,int 足够

    // Catalan(j) = (2j)! / (j! (j+1)!),j 最大取到 d-1,故阶乘只需到 2d
    int lim = 2 * d;
    fact[0] = 1;
    for (int i = 1; i <= lim; i++) fact[i] = fact[i - 1] * i % MOD;
    inv_fact[lim] = qpow(fact[lim], MOD - 2);
    for (int i = lim; i >= 1; i--) inv_fact[i - 1] = inv_fact[i] * i % MOD;

    for (int j = 0; j < d; j++) {
        ll cat = fact[2 * j] * inv_fact[j] % MOD * inv_fact[j + 1] % MOD;
        coef[j] = 2 * cat % MOD;
    }

    // 伴随矩阵:第一行放递推系数,次对角线全为 1
    Mat A;
    for (int j = 0; j < d; j++) A.a[0][j] = coef[j];
    for (int i = 1; i < d; i++) A.a[i][i - 1] = 1;

    // 初始状态 [h(0), h(-1), ..., h(1-d)] = [1, 0, ..., 0],
    // 于是 h(N) = (A^N)[0][0],无需单独构造初始向量。
    ll t = n / 2;
    Mat P = mpow(A, t);
    printf("%lld\n", P.a[0][0] % MOD);
    return 0;
}

复杂度

  • 时间:卡特兰数与系数 O(d)O(d);矩阵快速幂 O(d3log⁡N)O(d^3 \log N),其中 d=m/2⩽50d = m/2 \leqslant 50、 log⁡2N⩽29\log_2 N \leqslant 29,约 4×1064 \times 10^6 次乘加,C++ 实测在 10 ms 量级,远低于 1000 ms。
  • 空间:O(d2)O(d^2),即一个 50×5050 \times 50 的矩阵,几十 KB,远低于 256 MB。

总结

本题的难点全在识别结构而不在编码:先用「回到原点」把路径唯一切成独立的远足段, 消掉 DP 里那个 nn 维的「时刻」;再用 Dyck 路径把每段远足的条数压成卡特兰数; 最后才发现答案序列满足阶数仅为 m/2m/2 的常系数线性递推,从而把 O(nm)O(nm) 的 逐时刻 DP 换成 O(d3log⁡N)O(d^3 \log N) 的矩阵幂。写代码时有两个容易翻车的地方: 一是递推的阶数是 d=m/2d = m/2 而不是 mm(因为每段远足长必须是偶数、回到原点只在偶数时刻发生); 二是矩阵乘法的中间累加必须用 64 位并即时取模,否则 109×10910^9 \times 10^9 量级的乘积 在 int 上直接溢出。

同一模型的两个特例可以当校验用:m⩾nm \geqslant n 时约束失效,答案应为 (nn/2)\binom{n}{n/2}; m=2m = 2 时每段远足只能是 +1,−1+1,-1 或 −1,+1-1,+1,答案恰为 2n/22^{n/2}。