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包:…...
ES6从入门到精通:前言
ES6简介 ES6(ECMAScript 2015)是JavaScript语言的重大更新,引入了许多新特性,包括语法糖、新数据类型、模块化支持等,显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...
【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器
——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的一体化测试平台,覆盖应用全生命周期测试需求,主要提供五大核心能力: 测试类型检测目标关键指标功能体验基…...
为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?
在建筑行业,项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升,传统的管理模式已经难以满足现代工程的需求。过去,许多企业依赖手工记录、口头沟通和分散的信息管理,导致效率低下、成本失控、风险频发。例如&#…...
【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
Spring Boot面试题精选汇总
🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点睡觉 📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...
服务器--宝塔命令
一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行! sudo su - 1. CentOS 系统: yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...
C++使用 new 来创建动态数组
问题: 不能使用变量定义数组大小 原因: 这是因为数组在内存中是连续存储的,编译器需要在编译阶段就确定数组的大小,以便正确地分配内存空间。如果允许使用变量来定义数组的大小,那么编译器就无法在编译时确定数组的大…...
PAN/FPN
import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...
LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf
FTP 客服管理系统 实现kefu123登录,不允许匿名访问,kefu只能访问/data/kefu目录,不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...
