欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总帖：GESP认证C++编程真题解析 | 汇总
【题目来源】
洛谷：[P10376 GESP202403 六级] 游戏 - 洛谷
【题目描述】
你有四个正整数n , a , b , c n,a,b,cn,a,b,c，并准备用它们玩一个简单的小游戏。
在一轮游戏操作中，你可以选择将n nn减去a aa，或是将n nn减去b bb。游戏将会进行多轮操作，直到当n ≤ c n \leq cn≤c时游戏结束。
你想知道游戏结束时有多少种不同的游戏操作序列。两种游戏操作序列不同，当且仅当游戏操作轮数不同，或是某一轮游戏操作中，一种操作序列选择将n nn减去a aa，而另一种操作序列选择将n nn减去b bb。如果a = b a=ba=b，也认为将n nn减去a aa与将n nn减去b bb是不同的操作。
由于答案可能很大，你只需要求出答案对10 9 + 7 10^9 + 7109+7取模的结果。
【输入】
一行四个整数n , a , b , c n,a,b,cn,a,b,c。
【输出】
输出一行一个整数表示答案。
【输入样例】
1 1 1 1【输出样例】
1【算法标签】
《洛谷 P10376 游戏》 #动态规划DP# #深度优先搜索DFS# #记忆化搜索# #GESP# #2024#
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;constintmod=1e9+7;// 模数constintN=2e5+5;// 最大范围intn,a,b,c,ans;// n: 初始值, a,b: 减少值, c: 目标范围上限, ans: 答案intf[N<<1];// DP数组，大小为2N，通过+N来避免负数下标intmain(){// 输入参数cin>>n>>a>>b>>c;// 初始化：从n开始有1种方案f[n+N]=1;// 为了防止下标为负数，统一加N偏移量// 从n向下递推到c+1for(inti=n;i>c;i--){// 转移方程1：从i可以通过减a到达i-af[i-a+N]=(f[i-a+N]+f[i+N])%mod;// f[i-a] += f[i]// 转移方程2：从i可以通过减b到达i-bf[i-b+N]=(f[i-b+N]+f[i+N])%mod;// f[i-b] += f[i]}// 统计f[0]到f[c]的所有方案数之和for(inti=0;i<=N+c;i++)// 注意：这里应该是i <= c，但代码中有偏移{// 实际上，由于偏移N，f[i]对应原f[i-N]// 循环中的i是实际下标，需要减去N// 但代码直接累加f[i]，这意味着i的范围是0到N+c// 这似乎有问题ans=(ans+f[i])%mod;}// 输出结果cout<<ans<<endl;return0;}【运行结果】
114 51 4 1 176
