首页 > 试题广场 >

数列计算

[编程题]数列计算

热度指数：1644 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

已知一个正整数n，(3 <= n <= 15)，将所有n的乘方幂以及所有n的乘方幂（有限个且互不相等）之和组成一个递增序列。例如，当n为4时，该序列为：
1, 4, 5, 16, 17, 20, 21……
(4^0, 4^1, 4^0+4^1, 4^2, 4^0+4^2, 4^1+4^2, 4^0+4^1+4^2……)
请求出该序列的第K项(10进制)。

输入描述:

输入只有1行，为2个正整数，两数之间用一个空格隔开：
n K
(n, K的含义与上述描述一致, 且3<=n<=15, 10<=K<=1000)。

输出描述:

输出为计算结果，为一个正整数（注意在所有测试数据中，结果均不会超过2.1*10^9）。整数前不要有空格或其他任何符号。

示例1

输入

3 100

输出

算法知识视频讲解

Python

watle自动机

没看标签，直接考虑了DP解法

def getList(n, k):
    dp = [0] * (k + 1); dp[1] = 1;
    i = 2
    while i <= k:
        dp[i] = dp[i // 2] * n; i *= 2
    if dp[k] != 0:
        return dp[k]
    else:
        i = 3;
        while i <= k:
            start, end = 1, i - 1
            while i <= k and start < end:
                if dp[i] == 0:
                    dp[i] = dp[start] + dp[end]; i += 1; start += 1
            i += 1
        return dp[k]
    
if __name__ == "__main__":
    num = str(input()).split(" ")
    n, k = int(num[0]), int(num[1])
    print(getList(n, k))

发表于 2020-01-07 23:30:01 回复(0)