Python斐波拉契---本题python无解

解题思路:   事先说明，本题还没有其他人提供python解法，我也没能解决，这个参考代码不能正确通过题目。

                  本题有以下几个难点需要解决：

                （1）简单的递归耗时太长，会导致超时。需要用python的“字典”对递归算法进行优化，实现方式如参考代码第3---7行所示，原理是每计算一个数字，就将该数字存入字典，从而避免重复运算。

                （2）所给数据太大时，递归次数过多，超过了python的最大递归深度。解决方法是重新设定python的最大递归次数，如代码第1---2行所示。

                  188726462599566625    506424146244697409    288796655171361409

                  这组数字是本题提供的三组测试数据之一，经过测试，需要的递归次数在2600和2700之间，因此设置最大递归次数为3000，就不会报错。

                （3）结果数字过大，无法显示。这就是未解决的最后一个问题，尽管解决了递归次数过多的问题，但输入数据过大还是导致结果无法显示，程序进入递归后就会中断运行，不产生输出。

                  如果有同学知道如何解决，希望能在评论区留下方案，感激不尽。

                  PS：可能部分同学不熟悉斐波拉契数列，在这里说明一下，(fun(n+2)-1)是斐波拉契数列的前n项和公式，不用循环相加来计算前n项和是为了减少运行时间。

参考代码：

import sys 
sys.setrecursionlimit(3000)
d ={1:1,2:1}
def fun(n):
    if n in d:
        return d[n]
    else:
        d[n] = fun(n-1) + fun(n-2)
        return d[n]
n, m, p = map(int, input().split())
result = (fun(n+2)-1)%fun(m)%p
print(result)

                十几天后再回来更新一下，这段时间我去leetcode刷到了类似的题，学会了几种新方法，但即使是时间复杂度最低的矩阵快速幂也没法解决数据过大的问题，这道题用python应该是无解的。

                附上矩阵快速幂算法的代码：

def fib(n: int) -> int:
    if n < 2:
        return n
   
    q = [[1, 1], [1, 0]]
    res = matrix_pow(q, n - 1)
    return res[0][0]

def matrix_pow(a: list[list[int]], n: int) -> list[list[int]]:
    ret = [[1, 0], [0, 1]]
    while n > 0:
        if n & 1:
            ret = matrix_multiply(ret, a)
        n >>= 1
        a = matrix_multiply(a, a)
    return ret

def matrix_multiply(a: list[list[int]], b: list[list[int]]) -> list[list[int]]:
    c = [[0, 0], [0, 0]]
    for i in range(2):
        for j in range(2):
            c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j]
    return c

n, m, p = map(int, input().split())
result = (fib(n+2)-1) % fib(m) % p
print(result)

                这些代码在dot运行会报错，但在leetcode和我自己的vscode上是可以运行的。有空大家也可以去刷leetcode，那里的题解更详细，也不会出现某种语言无法解决所给问题的情况，这是leetcode解法的链接https://leetcode-cn.com/problems/fibonacci-number/solution/fei-bo-na-qi-shu-by-leetcode-solution-o4ze/

                另外评论区有同学给出了动态规划算法的代码，是很好的参考。