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

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

URL：入门教育赛3

题目描述

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

最后的结果对$10^9+7$取模。

输入格式

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

对于每一个样例：

第一行两个整数$n,k(1\le n,k\le 10^5)$。

数据保证$\sum n\le 3\times 10^5$。

输出格式

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

输入样例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}三种走法。

思路

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

初始化$dp[0]=1$。

状态转移方程为：$dp[i]={\sum }_{j=0}[k^j\le i]dp[j]$。

最后输出$dp[n]$。

每次转移时间复杂度为$O(log(i))$，于是总复杂度为$O(nlogn)$。

注意特判$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.夜游江滩的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---