网易2018校招内推编程题3 – 小易喜欢的数列

题目描述

背景

小易非常喜欢拥有以下性质的数列:
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

输出例子1

题目分析

动态规划,设dp[i][j]为数列长度为i且第一个数为j的合法数列数量。

dp[1][1~k]均为1,状态转移:dp[i][j] = sum(dp[i-1][x]),其中x >= j || (j % x) != 0

这样累加的话复杂度很高,有O(n * k * k),所以可以考虑求不合法数列的数量,用总数一减就是答案。

dp[i][j] = sum(dp[i-1][*]) - sum(dp[i][x]),其中x < j && (j % x) == 0sum(dp[i-1][*])只需要算一次,sum(dp[i][x])复杂度大概ln(k),所以总复杂度为O(n * k * log(k))

最后求sum(dp[n][*])就是答案。

代码实现方面可以用dp[i]去推dp[i+1],避免遍历。为了节省空间也可以上滚动数组,当然不用可是可以过的。

Java代码

PS:网易的这三道题很有做ACM题的感觉,虽然后两道没做出来挂了,补补题还是很爽的 = =

发表评论

电子邮件地址不会被公开。