GESP 题解库 / 6 级题解 / [GESP202403 六级] 游戏 · 第 18 / 27 题
GESP202403 六级 · P10376 · 简单

游戏

每次把 n 减去 a 或减去 b,直到 n ≤ c;数一数有多少种操作序列。

📊
n ≤ 2 × 10⁵
数值范围
🔢
long long
取模运算
⚡
O(n)
时间复杂度
🎯
线性递推(路径计数)
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

给定四个正整数 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 也视为不同操作

需要解决的问题

02
思维导图
整理解题思路的全貌
🎲 cnt[v] = cnt[v−a] + cnt[v−b]
🧠 状态
cnt[v]:从 v 开始的序列条数
答案 = cnt[n]
v 从 0 到 n 递推
规模 O(n)
📐 边界
v ≤ c → 游戏已结束
此时只剩空序列 → cnt[v] = 1
这是递推的"终止条件"
注意不是 0
🔁 转移
减 a → 走到 v−a
减 b → 走到 v−b
两种操作互不干扰,相加
a = b 时也要算两次
⚠️ 易错点
把 cnt[v ≤ c] 写成 0(应写 1)
忘记取模
a = b 时只算一次(应算两次)
用 int 存中间和(会溢出)
03
样例手算推导
样例的完整推演

🧮 样例 1:n = 1,a = 1,b = 1,c = 1

初始 n = 1 ≤ c = 1,游戏立刻结束。

1
边界直接命中

因为 n ≤ c,一次操作都不用做

只有"空序列"这 1 种

cnt[1] = 1

✅ 输出 1

这一组数据专门用来确认"空序列算 1 条"这个约定

🔑
为什么空序列要算 1 条?题目说"游戏将会进行多轮操作,直到当 n ≤ c 时游戏结束",并没有强制"必须至少操作一次"。所以当初始就满足 n ≤ c 时,"什么都不做的序列"就是一种合法的操作序列。

🧮 样例 2:n = 114,a = 51,b = 4,c = 1

这组数据的 a、b 差得很大,我们用递推来算(取模前先看结构)。

1
边界

对所有 v ≤ 1,cnt[v] = 1

即 cnt[0] = cnt[1] = 1

cnt[0..1] = 1

2
递推规律

对 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 的才有计数

3
最终结果

一路递推到 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;,那会引入错误。
04
解法对比
线性递推 vs 暴力枚举序列

⚔️ 解法对比

🟢 线性递推(推荐) 推荐

cnt[v] = cnt[v−a] + cnt[v−b],v 从 0 递推到 n

  • 时间 O(n)
  • n = 2 × 10⁵ 时约 2 × 10⁵
  • 代码 12 行
  • 空间 O(n)
💡
递推方向:从小的 v 往大的 v 推(因为 v−a、v−b 都更小)。也可以反过来理解为"倒着推",本质是同一件事。

🟠 枚举所有操作序列

递归/搜索生成所有可能的减 a、减 b 组合

  • 序列条数随 n 指数增长
  • n = 30 时已经不可行
  • 完全不能用于 n = 2 × 10⁵
  • 只能过极小数据
⚠️
为什么必须用 DP:本题的答案本身就是"序列条数",而这个条数会随 n 急剧增长(样例 3 的答案已经高达 3.8 亿)。所以只能"计数"而不能"枚举"。

📈 性能对比

方案复杂度可行性
线性递推O(n)✅ 稳过
枚举序列指数级❌ 不可行
05
算法流程图
从 0 递推到 n 的路径计数
开始读入 n、a、b、cv 从 0 遍历到 nv 是否不大于 c?是 ✓cnt[v] = 1否 ✗按递推式计算cnt[v] = get(v − a) + get(v − b),并对 10⁹+7 取模v 是否已经到 n?输出 cnt[n]v 加 1 递推下一个
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🎲 操作序列条数

输入 n a b c,程序会递推计算序列条数(演示规模内给出精确值)。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 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,游戏当场结束,只有"什么都不做"这一条序列。
如果这里写成 0,整个递推会全部算出 0——这是本题最容易踩的坑。

📖 关键几行怎么看

代码作用为什么这样写
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 时只加一次(题目明确规定要算作两种不同操作);④ 递推方向写反。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
1 1 1 11题面样例 1(初始就结束,空序列计 1)
114 51 4 1176题面样例 2
114514 191 9 810384178446题面样例 3(需取模)
5 1 1 116a = b = 1:从 v=2 起每步翻倍 → 2⁴ = 16
3 3 3 12一次操作就能结束(3 − 3 = 0 ≤ 1),两种操作各算一次
✅
自查清单:① 边界是 1 吗?② 每一步取模了吗?③ a = b 时算两次吗?

🚨 易错点清单

⚠️
边界写成 0:v ≤ c 时必须返回 1(空序列)。
⚠️
忘记取模:序列条数会非常大,必须每一步取模。
⚠️
a = b 只算一次:题目明确"减 a"与"减 b"算不同操作。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n)
空间复杂度
O(n)
n 最大
2 × 10⁵
运算量
约 2 × 10⁵

时间怎么算的?

空间都用在哪?

一个长度 n+1 的计数数组。

✅ 约 20 万次操作,瞬间完成。关键在于把"序列条数"看成可以递推的量。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 路径计数型递推的模板
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 条所有"到达终点即结束"的计数题
取模每步取模防溢出答案可能很大的计数题
🌟
思考题:如果题目改成"每次可以减去 a、b 或 c(三个选择)",递推式要改哪里?(提示:只需在转移里多加一项 get(v − c),其余完全不动。这说明"选择的数量"只影响转移式的项数,不影响整体的递推框架。)