gesp(C++六级)(7)洛谷:P10376:[GESP202403 六级] 游戏
gesp(C++六级)(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 a=b a=b,也认为将 n n n 减去 a a a 与将 n n n 减去 b b b 是不同的操作。
由于答案可能很大,你只需要求出答案对 1 0 9 + 7 10^9 + 7 109+7 取模的结果。
输入格式
一行四个整数 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 a=b=c=1 a=b=c=1, n ≤ 30 n \leq 30 n≤30。
- 对 40 % 40\% 40% 的数据, c = 1 c = 1 c=1, 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分)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
/*思路2: 动态规划:dp[i]含义:当n=i的方案数状态转移方程:当i<=c时,dp[i]=1; 当i>c时,dp[i]=dp[i-a]+dp[i-b]
*/
ll n,a,b,c;//注意开long long
ll dp[200010];//dp数组
const int N=1e9+7;
int main(){cin>>n>>a>>b>>c;//特判if(n<=c){cout<<1;return 0;} //递推for(int i=0;i<=c;i++) dp[i]=1;for(int i=c+1;i<=n;i++){
// dp[i]=(dp[i-a]%N+dp[i-b]%N)%N;//对比:注意这种写法没有考虑i-a和i-b可能为负数dp[i]=(dp[max(i-a,0ll)]%N+dp[max(i-b,0ll)]%N)%N;} //输出答案cout<<dp[n]; return 0;
}
文末彩蛋:
点击王老师青少年编程主页有更多精彩内容
相关文章:
gesp(C++六级)(7)洛谷:P10376:[GESP202403 六级] 游戏
gesp(C六级)(7)洛谷:P10376:[GESP202403 六级] 游戏 题目描述 你有四个正整数 n , a , b , c n,a,b,c n,a,b,c,并准备用它们玩一个简单的小游戏。 在一轮游戏操作中,你可以选择将 n n n 减去 a a a&am…...
随机森林例子
完整代码: # 导入必要的库 from sklearn.datasets import load_iris from sklearn.ensemble import RandomForestClassifier from sklearn.model_selection import train_test_split from sklearn.metrics import accuracy_score import numpy as np# 加载鸢尾花数…...
Qt中Widget及其子类的相对位置移动
Qt中Widget及其子类的相对位置移动 最后更新日期:2025.01.25 下面让我们开始今天的主题… 一、开启篇 提出问题:请看上图,我们想要实现的效果是控件黄色的Widge(m_infobarWidget)t随着可视化窗口(m_glWidge…...
MyBatis 关联映射详解
目录 一、创建表结构 1. 学生表 (student) 2. 教师表 (teacher) 二、一对一 & 多对一 关系映射 1. 连表查询(直接查询) 2. 分步查询(懒加载) 三、一对多 关系映射 1. 直接查询 2. 分步查询 四、MyBatis 延迟加载&am…...
Shell特殊位置变量以及常用内置变量总结
目录 1. 特殊的状态变量 1.1 $?(上一个命令的退出状态) 1.2 $$(当前进程的 PID) 1.3 $!(后台进程的 PID) 1.4 $_(上一条命令的最后一个参数) 2.常用shell内置变量 2.1 echo&…...
LeetCode:96.不同的二叉搜索树
跟着carl学算法,本系列博客仅做个人记录,建议大家都去看carl本人的博客,写的真的很好的! 代码随想录 LeetCode:96.不同的二叉搜索树 给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉…...
基于Springboot的智能学习平台系统【附源码】
基于Springboot的智能学习平台系统 效果如下: 系统登陆页面 系统主页面 课程详情页面 论坛页面 考试页面 试卷管理页面 考试记录页面 错题本页面 研究背景 随着互联网技术的普及,人们探索知识的方式逐渐转向数字化平台。传统的教学方法通常局限于固定…...
DeepSeek助力学术文献搜索!
搜集文献 宝子们如果是第一次发表学术论文,论文往往是会署名多个作者。在这种情况下,即便成功发表了论文,独立撰作或主导写作的挑战仍旧存在。那么,怎样才能独立地完成一篇属于自己的学术论文呢?对于初次尝试学术论文…...
阿里:基于路由和规划的多agent系统
📖标题:Talk to Right Specialists: Routing and Planning in Multi-agent System for Question Answering 🌐来源:arXiv, 2501.07813 🌟摘要 🔸利用大型语言模型(LLM),…...
@RestControllerAdvice 的作用
系列博客目录 文章目录 系列博客目录1.ControllerAdvice 有什么用主要功能 2.与 RestControllerAdvice 的区别3.苍穹外卖中的使用4.RestControllerAdvice可以指定范围吗(1)指定应用到某些包中的 RestController(2)指定应用到具有特…...
k均值聚类将数据分成多个簇
K-Means 聚类并将数据分成多个簇,可以使用以下方法: 实现思路 随机初始化 K 个聚类中心计算每个点到聚类中心的距离将点分配到最近的簇更新聚类中心重复上述过程直到收敛 完整代码: import torch import matplotlib.pyplot as pltdef kme…...
书生大模型实战营2
L0——入门岛 Python基础 Conda虚拟环境 虚拟环境是Python开发中不可或缺的一部分,它允许你在不同的项目中使用不同版本的库,避免依赖冲突。Conda是一个强大的包管理器和环境管理器。 创建新环境 首先,确保你已经安装了Anaconda或Minico…...
Excel 技巧21 - Excel中整理美化数据实例,Ctrl+T 超级表格(★★★)
本文讲Excel中如何整理美化数据的实例,以及CtrlT 超级表格的常用功能。 目录 1,Excel中整理美化数据 1-1,设置间隔行颜色 1-2,给总销量列设置数据条 1-3,根据总销量设置排序 1-4,加一个销售趋势列 2&…...
前端——js高级25.1.27
复习:对象 问题一: 多个数据的封装提 一个对象对应现实中的一个事物 问题二: 统一管理多个数据 问题三: 属性:组成:属性名属性值 (属性名为字符串,属性值任意) 方…...
学习数据结构(4)顺序表+单链表
1.顺序表算法题 题三: 2.单链表 (1)概念 链表是⼀种物理存储结构上非连续的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 (2)节点 节点的组成主要有两个部分:当前节点要保…...
GIS 中的 SQLAlchemy:空间数据与数据库之间的桥梁
利用 SQLAlchemy 在现代应用程序中无缝集成地理空间数据导言 地理信息系统(GIS)在管理城市规划、环境监测和导航系统等各种应用的空间数据方面发挥着至关重要的作用。虽然 PostGIS 或 SpatiaLite 等专业地理空间数据库在处理空间数据方面非常出色&#…...
python:斐索实验(Fizeau experiment)
斐索实验(Fizeau experiment)是在1851年由法国物理学家阿曼德斐索(Armand Fizeau)进行的一项重要实验,旨在测量光在移动介质中的传播速度。这项实验的结果对当时的物理理论产生了深远的影响,并且在后来的相…...
MySQL查询优化(三):深度解读 MySQL客户端和服务端协议
如果需要从 MySQL 服务端获得很高的性能,最佳的方式就是花时间研究 MySQL 优化和执行查询的机制。一旦理解了这些,大部分的查询优化是有据可循的,从而使得整个查询优化的过程更有逻辑性。下图展示了 MySQL 执行查询的过程: 客户端…...
vue3相关知识点
title: vue_1 date: 2025-01-28 12:00:00 tags:- 前端 categories:- 前端vue3 Webpack ~ vite vue3是基于vite创建的 vite 更快一点 一些准备工作 准备后如图所示 插件 Main.ts // 引入createApp用于创建应用 import {createApp} from vue // 引入App根组件 import App f…...
基于springboot+vue的流浪动物救助系统的设计与实现
开发语言:Java框架:springbootJDK版本:JDK1.8服务器:tomcat7数据库:mysql 5.7(一定要5.7版本)数据库工具:Navicat11开发软件:eclipse/myeclipse/ideaMaven包:…...
Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...
k8s从入门到放弃之Ingress七层负载
k8s从入门到放弃之Ingress七层负载 在Kubernetes(简称K8s)中,Ingress是一个API对象,它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress,你可…...
汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...
基于Docker Compose部署Java微服务项目
一. 创建根项目 根项目(父项目)主要用于依赖管理 一些需要注意的点: 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件,否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...
浪潮交换机配置track检测实现高速公路收费网络主备切换NQA
浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求,本次涉及的主要是收费汇聚交换机的配置,浪潮网络设备在高速项目很少,通…...
面向无人机海岸带生态系统监测的语义分割基准数据集
描述:海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而,目前该领域仍面临一个挑战,即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...
人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式
今天是关于AI如何在教学中增强学生的学习体验,我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育,这并非炒作,而是已经发生的巨大变革。教育机构和教育者不能忽视它,试图简单地禁止学生使…...
代码规范和架构【立芯理论一】(2025.06.08)
1、代码规范的目标 代码简洁精炼、美观,可持续性好高效率高复用,可移植性好高内聚,低耦合没有冗余规范性,代码有规可循,可以看出自己当时的思考过程特殊排版,特殊语法,特殊指令,必须…...
2025年低延迟业务DDoS防护全攻略:高可用架构与实战方案
一、延迟敏感行业面临的DDoS攻击新挑战 2025年,金融交易、实时竞技游戏、工业物联网等低延迟业务成为DDoS攻击的首要目标。攻击呈现三大特征: AI驱动的自适应攻击:攻击流量模拟真实用户行为,差异率低至0.5%,传统规则引…...
医疗AI模型可解释性编程研究:基于SHAP、LIME与Anchor
1 医疗树模型与可解释人工智能基础 医疗领域的人工智能应用正迅速从理论研究转向临床实践,在这一过程中,模型可解释性已成为确保AI系统被医疗专业人员接受和信任的关键因素。基于树模型的集成算法(如RandomForest、XGBoost、LightGBM)因其卓越的预测性能和相对良好的解释性…...
