每次把 n 减去 a 或减去 b,直到 n ≤ c;数一数有多少种操作序列。
给定四个正整数 n、a、b、c。每轮操作可以把 n 减去 a 或减去 b,直到 n ≤ c 时游戏结束。问游戏结束时共有多少种不同的操作序列。(若 a = b,"减 a"与"减 b"仍视为不同的操作。)答案对 10⁹ + 7 取模。
cnt[v] = 从当前值为 v 开始、游戏彻底结束的序列条数。v ≤ c 游戏已经结束——此时空序列算 1 条;否则 cnt[v] = cnt[v − a] + cnt[v − b]。cnt[n],一次线性递推即可,复杂度 O(n)。路径计数线性递推取模边界处理
| 项目 | 说明 |
|---|---|
| 输入 | 一行四个整数 n、a、b、c |
| 输出 | 序列条数对 10⁹+7 取模 |
| 数据范围 | 1 ≤ a, b, c ≤ n ≤ 2 × 10⁵ |
| 结束条件 | n ≤ c 时立即结束 |
| 注意 | 即使 a = b,减 a 与减 b 也视为不同操作 |
cnt[v]:从数值 v 开始能产生的序列条数v ≤ c 时游戏已结束,只剩"什么都不做"这 1 条空序列初始 n = 1 ≤ c = 1,游戏立刻结束。
因为 n ≤ c,一次操作都不用做
只有"空序列"这 1 种
cnt[1] = 1
✅ 输出 1
这一组数据专门用来确认"空序列算 1 条"这个约定
n ≤ c 时游戏结束",并没有强制"必须至少操作一次"。所以当初始就满足 n ≤ c 时,"什么都不做的序列"就是一种合法的操作序列。这组数据的 a、b 差得很大,我们用递推来算(取模前先看结构)。
对所有 v ≤ 1,cnt[v] = 1
即 cnt[0] = cnt[1] = 1
cnt[0..1] = 1
对 v > 1:cnt[v] = cnt[v − 51] + cnt[v − 4]
(当 v − 51 < 0 时那一项按 0 计)
例如 cnt[2] = cnt[−49] + cnt[−2] = 0 + 0 = 0
cnt[3] = 0 + 0 = 0
cnt[4] = cnt[−47] + cnt[0] = 0 + 1 = 1
cnt[5] = cnt[−46] + cnt[1] = 0 + 1 = 1
cnt[6] = 0 + cnt[2] = 0
cnt[7] = 0 + cnt[3] = 0
cnt[8] = 0 + cnt[4] = 1
cnt[9] = 0 + cnt[5] = 1
…(可以看出来值与模 4 的余数有关)
规律:只有能走到 ≤ c 的才有计数
一路递推到 v = 114
cnt[114] = 176
(过程中每一步都取模 10⁹+7)
✅ 输出 176
这是本题最容易被忽略的细节:如果当前 v > c,而减去 a 之后得到 v − a < 0,那么这个结果显然也满足 ≤ c——游戏照样结束。
所以判定条件应该写成"v − a ≤ c 就计 1 条",而不是"先检查是否为负数、负数就返回 0"。把负数误判成 0,会漏掉一大批合法序列——例如样例 2 的答案就会从 176 变成 10。
get(v) = (v <= c) ? 1 : cnt[v],它天然覆盖了负数情形(因为负数一定 ≤ c),从而避免下标越界、也不会漏解。if (v < 0) return 0;,那会引入错误。cnt[v] = cnt[v−a] + cnt[v−b],v 从 0 递推到 n
v−a、v−b 都更小)。也可以反过来理解为"倒着推",本质是同一件事。递归/搜索生成所有可能的减 a、减 b 组合
| 方案 | 复杂度 | 可行性 |
|---|---|---|
| 线性递推 | O(n) | ✅ 稳过 |
| 枚举序列 | 指数级 | ❌ 不可行 |
输入 n a b c,程序会递推计算序列条数(演示规模内给出精确值)。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; const long long MOD = 1000000007LL; long long cnt[200005]; int main() { int n, a, b, c; scanf("%d %d %d %d", &n, &a, &b, &c); auto get = [&](int v) -> long long { // 只要减完之后 v <= c 就算游戏结束(减成负数也一样结束) if (v <= c) return 1; // 已结束:只剩空序列 1 条 return cnt[v]; }; for (int v = 0; v <= n; v++) { if (v <= c) cnt[v] = 1; else cnt[v] = (get(v - a) + get(v - b)) % MOD; } printf("%lld\n", cnt[n]); return 0; }
v ≤ c 时取 1 而不是 0?因为 cnt[v] 的定义是"从 v 开始、游戏结束时的序列条数"。若 v 已经 ≤ c,游戏当场结束,只有"什么都不做"这一条序列。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
if (v < 0) return 0; | 越界保护 | 走不到的分支计 0 |
if (v <= c) return 1; | 终止条件 | 已结束 → 空序列 1 条 |
cnt[v] = get(v-a) + get(v-b) | 转移 | 两种操作分别产生各自的后续序列 |
% MOD | 取模 | 防止溢出 |
v ≤ c 写成返回 0;② 忘记取模(中间和会超出 long long);③ a = b 时只加一次(题目明确规定要算作两种不同操作);④ 递推方向写反。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
1 1 1 1 | 1 | 题面样例 1(初始就结束,空序列计 1) |
114 51 4 1 | 176 | 题面样例 2 |
114514 191 9 810 | 384178446 | 题面样例 3(需取模) |
5 1 1 1 | 16 | a = b = 1:从 v=2 起每步翻倍 → 2⁴ = 16 |
3 3 3 1 | 2 | 一次操作就能结束(3 − 3 = 0 ≤ 1),两种操作各算一次 |
v ≤ c 时必须返回 1(空序列)。一个长度 n+1 的计数数组。
✅ 约 20 万次操作,瞬间完成。关键在于把"序列条数"看成可以递推的量。
// 路径计数型递推的模板 long long get(int v) { if (v < 0) return 0; if (v <= c) return 1; // 终止状态 return cnt[v]; } for (int v = 0; v <= n; v++) cnt[v] = (v <= c) ? 1 : (get(v - a) + get(v - b)) % MOD; // 同类问题:走台阶 // 每次走 1 级或 2 级,走到第 n 级有多少种走法 // f[0] = f[1] = 1; f[i] = f[i-1] + f[i-2]; // 与本题的递推形式完全一致,区别只在"终止条件" // 关键思维:问"有多少种方案"时,优先想递推/DP // 因为方案数往往很大,枚举不可行,但计数可以递推
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 路径计数 | cnt[v] = Σ cnt[后继] | 走台阶、掷骰子、操作序列计数 |
| 终止条件取 1 | 已结束 = 空方案 1 条 | 所有"到达终点即结束"的计数题 |
| 取模 | 每步取模防溢出 | 答案可能很大的计数题 |
get(v − c),其余完全不动。这说明"选择的数量"只影响转移式的项数,不影响整体的递推框架。)