游戏 题解

题目分析

本题要求计算从整数 $n$ 出发，每次选择减去 $a$ 或减去 $b$，直到当前值 $\le c$ 时停止，所有可能的操作序列总数。由于每次操作有两种选择（即使 $a=b$，减去 $a$ 和减去 $b$ 也视为不同操作），我们需要统计所有长度不同或某一步选择不同的序列。

题目数据范围：$1 \le a,b,c \le n \le 2\times10^5$，并要求对 $10^9+7$ 取模。

解题思路

本题是一个典型的动态规划 / 记忆化搜索问题。

设 $f[i]$ 表示当前数值为 $i$ 时，游戏结束（即最终值 $\le c$）的不同操作序列数。显然：

• 当 $i \le c$ 时：游戏已经结束，不需要任何操作。此时只有一种方案（空序列）。即 $f[i] = 1$。
• 当 $i>c$ 时：可以进行一轮操作，有两种选择：
  • 选择减去 $a$，随后从 $i-a$ 继续游戏，后续方案数为 $f[i-a]$；
  • 选择减去 $b$，随后从 $i-b$ 继续游戏，后续方案数为 $f[i-b]$。

两种选择互斥，因此：

我们要的答案就是 $f[n]$。

注意：

• 即使 $a=b$，由于题目要求区分这两类操作，我们依然将两个选择独立相加。
• 如果 $i-a$ 或 $i-b \le c$（包括可能的负数情况），游戏立即结束，对应的方案数就是 $1$。

算法说明

1. 记忆化搜索（参考代码）

使用递归函数 dfs(x)，返回从 $x$ 开始到结束的方案数：

• 基础情形：x <= c 时返回 1；
• 若之前已经计算过，则直接返回记忆化数组中的值；
• 否则递归计算 (dfs(x-a) + dfs(x-b)) % mod 并存储后返回。

cpp
复制
1#include<bits/stdc++.h>
2using namespace std;
3long long an[200005]={0};
4long long n,c,b,a;
5const int mod=1e9+7;
6long long dfs(long long x){
7    if(x <= c) return 1;
8    if(an[x] != 0) return an[x];
9    return an[x] = (dfs(x-a) + dfs(x-b)) % mod;
10}
11int main(){
12    cin >> n >> a >> b >> c;
13    cout << dfs(n);
14    return 0;
15}

说明：an[x] 存储 $f[x]$ 的值。由于递归深度可能达到 $n=2\times10^5$ 级别，在某些环境下可能会造成递归栈溢出。因此更加推荐使用下面的迭代动态规划方法，既安全又高效。

2. 迭代动态规划（推荐写法）

我们可以将递归过程反转，从 $i=c+1$ 向上递推到 $n$。

转移方程不变：

但在递推时，若 $i-a \le c$，则该项贡献为 $1$，否则为 $f[i-a]$（同理处理 $b$）。

代码实现：

cpp
复制
1#include <bits/stdc++.h>
2using namespace std;
3
4const int MOD = 1e9 + 7;
5const int MAXN = 200005;
6
7long long f[MAXN];
8
9int main() {
10    ios::sync_with_stdio(false);
11    cin.tie(nullptr);
12
13    int n, a, b, c;
14    cin >> n >> a >> b >> c;
15
16    // 初始化 i <= c 的情况
17    for (int i = 0; i <= c; ++i) {
18        f[i] = 1;
19    }
20
21    // 递推计算
22    for (int i = c + 1; i <= n; ++i) {
23        // 减去 a 的选择
24        long long wayA = (i - a <= c) ? 1 : f[i - a];
25        // 减去 b 的选择
26        long long wayB = (i - b <= c) ? 1 : f[i - b];
27        f[i] = (wayA + wayB) % MOD;
28    }
29
30    cout << f[n] << "\n";
31    return 0;
32}

时间复杂度分析

• 状态数：只有 $i = c+1 \sim n$ 需要计算，共 $O(n)$ 个状态。
• 单次转移：每个状态 $O(1)$ 计算。

因此总时间复杂度为 $O(n)$，空间复杂度 $O(n)$，完全满足 $n \le 2\times10^5$ 的要求。

总结

本题把游戏过程抽象为一个简单的状态转移模型，通过动态规划或记忆化搜索即可高效求解。解题时需注意：

1. 基础情形 $i \le c$ 的值为 $1$；
2. $a=b$ 时操作仍按不同处理，直接相加；
3. 递推时注意数组下标的范围，可以用条件判断避免负数下标；
4. 当数据规模较大时，优先采用迭代 DP 防止栈溢出。