把路径唯一拆成若干段「远足」,每段长 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
形式化题目
在数轴上的整数点做随机游走:时刻
求满足条件的走法条数,对
数据范围:
正解
思路
朴素做法。 直接按题面定义 DP:状态记「当前位置
瓶颈在哪? 状态里同时带着「在哪里」和「出门多久」,两个维度都被
关键观察一:路径唯一分解成「远足」。 每当路径回到
其中
关键观察二:
用
关键观察三:
答案是
转移矩阵。 取状态向量
构造
初始状态取
以样例
数据说明。 本题素材来自信息学奥赛一本通《高手训练篇》,其
data/目录附带 生成脚本data.py,即测试数据是按题面自造的,出题意图与官方原题可能存在偏差。 本解已直接用该data/的 10 个.in点逐点核对.out,全部一致。
代码
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++ 版(同一算法):
/**
* 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;
}复杂度
- 时间:卡特兰数与系数
;矩阵快速幂 ,其中 、 ,约 次乘加,C++ 实测在 10 ms 量级,远低于 1000 ms。 - 空间:
,即一个 的矩阵,几十 KB,远低于 256 MB。
总结
本题的难点全在识别结构而不在编码:先用「回到原点」把路径唯一切成独立的远足段,
消掉 DP 里那个 int 上直接溢出。
同一模型的两个特例可以当校验用: