首页 > 试题广场 >

小易喜欢的数列

[编程题]小易喜欢的数列
  • 热度指数：11379 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
小易非常喜欢拥有以下性质的数列:
1、数列的长度为n
2、数列中的每个数都在1到k之间(包括1和k)
3、对于位置相邻的两个数A和B(A在B前),都满足(A <= B)或(A mod B != 0)(满足其一即可)
例如,当n = 4, k = 7
那么{1,7,7,2},它的长度是4,所有数字也在1到7范围内,并且满足第三条性质,所以小易是喜欢这个数列的
但是小易不喜欢{4,4,4,2}这个数列。小易给出n和k,希望你能帮他求出有多少个是他会喜欢的数列。

输入描述:
输入包括两个整数n和k(1 ≤ n ≤ 10, 1 ≤ k ≤ 10^5)


输出描述:
输出一个整数,即满足要求的数列个数,因为答案可能很大,输出对1,000,000,007取模的结果。
示例1

输入

2 2

输出

3
算法知识视频讲解
开通博客
头像 海789
发表于 2021-09-24 14:02:42
#include<iostream> #include<vector> using namespace std; int main(){ //dp[i][j]表示的含义是前i个整数，以j结尾的时候，有多少喜欢的数列 //转义方程dp[i][j] = sum 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 bandiaoz
发表于 2024-12-20 15:51:04
解题思路 这是一个动态规划问题，需要计算满足条件的数列个数 定义 表示长度为 且最后一个数字为 的合法数列个数 对于每个位置，我们需要： 统计前一个位置所有数字的方案总和 减去不满足条件的方案数（即对于当前数 ，减去所有是 倍数位置的方案数） 最终答案是最后一行所有位置的方案数之和 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 动态规划 网易 2018 Java工程师
来自：网易2018校招内推编...
上传者：小小
难度：
58条回答 21733浏览

热门推荐

通过挑战的用户

查看代码

相关试题

小易喜欢的数列

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号