[补题记录] 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

相关文章

国内环境搭建私有知识问答库踩坑记录(ollama+deepseek+ragflow)

《国内环境搭建私有知识问答库踩坑记录(ollama+deepseek+ragflow)》本文给大家利用deepseek模型搭建私有知识问答库的详细步骤和遇到的问题及解决办法,感兴趣的朋友一起看看吧... 目录1. 第1步大家在安装完ollama后,需要到系统环境变量中添加两个变量2. 第3步 “在cmd中

Python FastAPI入门安装使用

《PythonFastAPI入门安装使用》FastAPI是一个现代、快速的PythonWeb框架,用于构建API,它基于Python3.6+的类型提示特性,使得代码更加简洁且易于绶护,这篇文章主要介... 目录第一节:FastAPI入门一、FastAPI框架介绍什么是ASGI服务(WSGI)二、FastAP

Spring Retry 实现乐观锁重试实践记录

《SpringRetry实现乐观锁重试实践记录》本文介绍了在秒杀商品SKU表中使用乐观锁和MybatisPlus配置乐观锁的方法,并分析了测试环境和生产环境的隔离级别对乐观锁的影响,通过简单验证,... 目录一、场景分析 二、简单验证 2.1、可重复读 2.2、读已提交 三、最佳实践 3.1、配置重试模板

在 Spring Boot 中使用异步线程时的 HttpServletRequest 复用问题记录

《在SpringBoot中使用异步线程时的HttpServletRequest复用问题记录》文章讨论了在SpringBoot中使用异步线程时,由于HttpServletRequest复用导致... 目录一、问题描述:异步线程操作导致请求复用时 Cookie 解析失败1. 场景背景2. 问题根源二、问题详细分

关于Spring @Bean 相同加载顺序不同结果不同的问题记录

《关于Spring@Bean相同加载顺序不同结果不同的问题记录》本文主要探讨了在Spring5.1.3.RELEASE版本下,当有两个全注解类定义相同类型的Bean时,由于加载顺序不同,最终生成的... 目录问题说明测试输出1测试输出2@Bean注解的BeanDefiChina编程nition加入时机总结问题说明

将sqlserver数据迁移到mysql的详细步骤记录

《将sqlserver数据迁移到mysql的详细步骤记录》:本文主要介绍将SQLServer数据迁移到MySQL的步骤,包括导出数据、转换数据格式和导入数据,通过示例和工具说明,帮助大家顺利完成... 目录前言一、导出SQL Server 数据二、转换数据格式为mysql兼容格式三、导入数据到MySQL数据

关于rpc长连接与短连接的思考记录

《关于rpc长连接与短连接的思考记录》文章总结了RPC项目中长连接和短连接的处理方式,包括RPC和HTTP的长连接与短连接的区别、TCP的保活机制、客户端与服务器的连接模式及其利弊分析,文章强调了在实... 目录rpc项目中的长连接与短连接的思考什么是rpc项目中的长连接和短连接与tcp和http的长连接短

Oracle查询优化之高效实现仅查询前10条记录的方法与实践

《Oracle查询优化之高效实现仅查询前10条记录的方法与实践》:本文主要介绍Oracle查询优化之高效实现仅查询前10条记录的相关资料,包括使用ROWNUM、ROW_NUMBER()函数、FET... 目录1. 使用 ROWNUM 查询2. 使用 ROW_NUMBER() 函数3. 使用 FETCH FI

Python MySQL如何通过Binlog获取变更记录恢复数据

《PythonMySQL如何通过Binlog获取变更记录恢复数据》本文介绍了如何使用Python和pymysqlreplication库通过MySQL的二进制日志(Binlog)获取数据库的变更记录... 目录python mysql通过Binlog获取变更记录恢复数据1.安装pymysqlreplicat

Servlet中配置和使用过滤器的步骤记录

《Servlet中配置和使用过滤器的步骤记录》:本文主要介绍在Servlet中配置和使用过滤器的方法,包括创建过滤器类、配置过滤器以及在Web应用中使用过滤器等步骤,文中通过代码介绍的非常详细,需... 目录创建过滤器类配置过滤器使用过滤器总结在Servlet中配置和使用过滤器主要包括创建过滤器类、配置过滤