[补题记录] StarryCoding 入门教育赛3 E.夜游江滩

2024-05-10 22:44

本文主要是介绍[补题记录] StarryCoding 入门教育赛3 E.夜游江滩,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

URL:入门教育赛3

题目描述

e e e宝和桶子晚上吃太饱没事做决定到江边散步减肥,他们在江滩的起始点(位置为 0 0 0),要走到江滩的尽头(位置为 n n n),由于他们腿特别长,一步可以走 1 , k , k 2 , k 3 . . . 1,k,k^2,k^3... 1,k,k2,k3...的距离,他们想知道走到尽头一共有多少种走法。

最后的结果对 1 0 9 + 7 10^9+7 109+7取模。

输入格式

第一行一个整数 T ( 1 ≤ T ≤ 100 ) T(1 \le T \le 100) T(1T100)表示样例个数。

对于每一个样例:

第一行两个整数 n , k ( 1 ≤ n , k ≤ 1 0 5 ) n, k(1 \le n, k \le 10^5) n,k(1n,k105)

数据保证 ∑ n ≤ 3 × 1 0 5 \sum n \le 3 \times 10^5 n3×105

输出格式

对于每组测试样例,一个整数表示结果。

输入样例1

2
3 2
5 3

输出样例1

3
4

解释

对于第二组样例,有 { 1 , 1 , 3 } , { 1 , 3 , 1 } , { 3 , 1 , 1 } , { 1 , 1 , 1 , 1 , 1 } \{1, 1, 3\}, \{1, 3, 1\}, \{3, 1, 1\}, \{1, 1, 1, 1, 1\} {1,1,3},{1,3,1},{3,1,1},{1,1,1,1,1}三种走法。

思路

定义 d p [ i ] dp[i] dp[i]表示从 0 0 0走到 i i i的方案数。

初始化 d p [ 0 ] = 1 dp[0] = 1 dp[0]=1

状态转移方程为: d p [ i ] = ∑ j = 0 [ k j ≤ i ] d p [ j ] dp[i] = \sum_{j=0}[k^j \le i]dp[j] dp[i]=j=0[kji]dp[j]

最后输出 d p [ n ] dp[n] dp[n]

每次转移时间复杂度为 O ( l o g ( i ) ) O(log(i)) O(log(i)),于是总复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)

注意特判 k = 1 k = 1 k=1的情况。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 9;
ll dp[N];
const ll p = 1e9 + 7;void solve()
{int n, k;cin >> n >> k;if(k == 1){cout << 1 << '\n';return;}dp[0] = 1;for (int i = 1; i <= n; ++i){dp[i] = 0;}for (int i = 1; i <= n; ++i){for (ll j = 1; j <= i; j *= k){dp[i] = (dp[i] + dp[i - j]) % p;}}cout << dp[n] << "\n";
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int _;cin >> _;while (_--)solve();return 0;
}

这篇关于[补题记录] StarryCoding 入门教育赛3 E.夜游江滩的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/977773

相关文章

从入门到精通MySQL联合查询

《从入门到精通MySQL联合查询》:本文主要介绍从入门到精通MySQL联合查询,本文通过实例代码给大家介绍的非常详细,需要的朋友可以参考下... 目录摘要1. 多表联合查询时mysql内部原理2. 内连接3. 外连接4. 自连接5. 子查询6. 合并查询7. 插入查询结果摘要前面我们学习了数据库设计时要满

从入门到精通C++11 <chrono> 库特性

《从入门到精通C++11<chrono>库特性》chrono库是C++11中一个非常强大和实用的库,它为时间处理提供了丰富的功能和类型安全的接口,通过本文的介绍,我们了解了chrono库的基本概念... 目录一、引言1.1 为什么需要<chrono>库1.2<chrono>库的基本概念二、时间段(Durat

在Spring Boot中集成RabbitMQ的实战记录

《在SpringBoot中集成RabbitMQ的实战记录》本文介绍SpringBoot集成RabbitMQ的步骤,涵盖配置连接、消息发送与接收,并对比两种定义Exchange与队列的方式:手动声明(... 目录前言准备工作1. 安装 RabbitMQ2. 消息发送者(Producer)配置1. 创建 Spr

解析C++11 static_assert及与Boost库的关联从入门到精通

《解析C++11static_assert及与Boost库的关联从入门到精通》static_assert是C++中强大的编译时验证工具,它能够在编译阶段拦截不符合预期的类型或值,增强代码的健壮性,通... 目录一、背景知识:传统断言方法的局限性1.1 assert宏1.2 #error指令1.3 第三方解决

从入门到精通MySQL 数据库索引(实战案例)

《从入门到精通MySQL数据库索引(实战案例)》索引是数据库的目录,提升查询速度,主要类型包括BTree、Hash、全文、空间索引,需根据场景选择,建议用于高频查询、关联字段、排序等,避免重复率高或... 目录一、索引是什么?能干嘛?核心作用:二、索引的 4 种主要类型(附通俗例子)1. BTree 索引(

Redis 配置文件使用建议redis.conf 从入门到实战

《Redis配置文件使用建议redis.conf从入门到实战》Redis配置方式包括配置文件、命令行参数、运行时CONFIG命令,支持动态修改参数及持久化,常用项涉及端口、绑定、内存策略等,版本8... 目录一、Redis.conf 是什么?二、命令行方式传参(适用于测试)三、运行时动态修改配置(不重启服务

k8s上运行的mysql、mariadb数据库的备份记录(支持x86和arm两种架构)

《k8s上运行的mysql、mariadb数据库的备份记录(支持x86和arm两种架构)》本文记录在K8s上运行的MySQL/MariaDB备份方案,通过工具容器执行mysqldump,结合定时任务实... 目录前言一、获取需要备份的数据库的信息二、备份步骤1.准备工作(X86)1.准备工作(arm)2.手

MySQL DQL从入门到精通

《MySQLDQL从入门到精通》通过DQL,我们可以从数据库中检索出所需的数据,进行各种复杂的数据分析和处理,本文将深入探讨MySQLDQL的各个方面,帮助你全面掌握这一重要技能,感兴趣的朋友跟随小... 目录一、DQL 基础:SELECT 语句入门二、数据过滤:WHERE 子句的使用三、结果排序:ORDE

SpringBoot3应用中集成和使用Spring Retry的实践记录

《SpringBoot3应用中集成和使用SpringRetry的实践记录》SpringRetry为SpringBoot3提供重试机制,支持注解和编程式两种方式,可配置重试策略与监听器,适用于临时性故... 目录1. 简介2. 环境准备3. 使用方式3.1 注解方式 基础使用自定义重试策略失败恢复机制注意事项

Python UV安装、升级、卸载详细步骤记录

《PythonUV安装、升级、卸载详细步骤记录》:本文主要介绍PythonUV安装、升级、卸载的详细步骤,uv是Astral推出的下一代Python包与项目管理器,主打单一可执行文件、极致性能... 目录安装检查升级设置自动补全卸载UV 命令总结 官方文档详见:https://docs.astral.sh/