如何用py的快速幂求这道题

P1255 数楼梯

ironwaste @ 2024-07-24 00:57:06

import numpy as np

n = (int)(input());
# print(n)
# n = long(n)
res = np.eye(2);
res = res.astype(long)
# print(res)
n -= 1
a = np.array([[1,1],[1,0]])
a = a.astype(long)

# print(a)

while(n) :
    if (n & 1) : res = np.dot(res,a)
    # print(a)
    # print(n)
    a = np.dot(a,a)
    n>>=1
# print(res)
print("%ld"%(res[0][0] + res[1][0]))

这个代码和c++ 的错误都是一样的没有高精度，只能够过60分，能不能把这个进行修改类型成字符串那种可加的？

by Eleveslaine @ 2024-07-24 01:24:21

直接用 Python 自带的 int 就好，这玩意自带高精。

by Maisie586_ @ 2024-07-24 07:32:20

@ironwaste97213 你这代码全RE啊

by ironwaste @ 2024-07-24 12:17:58

@Maisie586_ 贴错代码了ww这个能过60

import numpy as np

n = (int)(input());
# print(n)
# n = long(n)
res = np.eye(2);

# print(res)
n -= 1
a = np.array([[1,1],[1,0]])

# print(a)

while(n) :
    if (n & 1) : res = np.dot(res,a)
    # print(a)
    # print(n)
    a = np.dot(a,a)
    n>>=1
# print(res)
print("%d"%(res[0][0] + res[1][0]))

by ironwaste @ 2024-07-24 12:19:38

@SlaineTroyard 确实但是我想用矩阵快速幂来搞这个，但是好像numpy的库里面最高支支持uint32或者float32，就用矩阵的dot去写就写不出来了，我想知道矩阵库能不能有这种直接高精的方式？

by Maisie586_ @ 2024-07-24 12:21:38

@ironwaste97213 求关（DP+快速幂

def climb_stairs(n):
    if n <= 2:
        return n
    dp = [0] * (n + 1)
    dp[0], dp[1] = 1, 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

n = int(input())
print(climb_stairs(n))

by ironwaste @ 2024-07-24 20:26:17

@Maisie586_ 啊？这也没有dp和矩阵快速幂啊