网站最近收录,百度官网首页登陆,在哪个网站可以做图文合并,省建设厅网站安徽gesp(C六级)#xff08;7#xff09;洛谷#xff1a;P10376#xff1a;[GESP202403 六级] 游戏 题目描述
你有四个正整数 n , a , b , c n,a,b,c n,a,b,c#xff0c;并准备用它们玩一个简单的小游戏。
在一轮游戏操作中#xff0c;你可以选择将 n n n 减去 a a a六级)7洛谷P10376[GESP202403 六级] 游戏 题目描述
你有四个正整数 n , a , b , c n,a,b,c n,a,b,c并准备用它们玩一个简单的小游戏。
在一轮游戏操作中你可以选择将 n n n 减去 a a a或是将 n n n 减去 b b b。游戏将会进行多轮操作直到当 n ≤ c n \leq c n≤c 时游戏结束。
你想知道游戏结束时有多少种不同的游戏操作序列。两种游戏操作序列不同当且仅当游戏操作轮数不同或是某一轮游戏操作中一种操作序列选择将 n n n 减去 a a a而另一种操作序列选择将 n n n 减去 b b b。如果 a b ab ab也认为将 n n n 减去 a a a 与将 n n n 减去 b b b 是不同的操作。
由于答案可能很大你只需要求出答案对 1 0 9 7 10^9 7 1097 取模的结果。
输入格式
一行四个整数 n , a , b , c n,a,b,c n,a,b,c。
输出格式
输出一行一个整数表示答案。
样例 #1
样例输入 #1
1 1 1 1样例输出 #1
1样例 #2
样例输入 #2
114 51 4 1样例输出 #2
176样例 #3
样例输入 #3
114514 191 9 810样例输出 #3
384178446提示
数据规模与约定
对 20 % 20\% 20% 的数据 a b c 1 abc1 abc1 n ≤ 30 n \leq 30 n≤30。对 40 % 40\% 40% 的数据 c 1 c 1 c1 n ≤ 1 0 3 n \leq 10^3 n≤103。对全部的测试数据保证 1 ≤ a , b , c ≤ n ≤ 2 × 1 0 5 1 \leq a,b,c \leq n \leq 2 \times 10^5 1≤a,b,c≤n≤2×105。 AC代码100分 #includebits/stdc.h
using namespace std;
#define ll long long
/*思路2 动态规划dp[i]含义:当ni的方案数状态转移方程当ic时dp[i]1; 当ic时dp[i]dp[i-a]dp[i-b]
*/
ll n,a,b,c;//注意开long long
ll dp[200010];//dp数组
const int N1e97;
int main(){cinnabc;//特判if(nc){cout1;return 0;} //递推for(int i0;ic;i) dp[i]1;for(int ic1;in;i){
// dp[i](dp[i-a]%Ndp[i-b]%N)%N;//对比注意这种写法没有考虑i-a和i-b可能为负数dp[i](dp[max(i-a,0ll)]%Ndp[max(i-b,0ll)]%N)%N;} //输出答案coutdp[n]; return 0;
}文末彩蛋 点击王老师青少年编程主页有更多精彩内容
