1444: 蓝桥杯2014年第五届真题-斐波那契(python)

A矩阵分解示例

def mm_yu(x,y,mod):
    a =[[0,0],[0,0]]
    for i in range(2):
        for j in range(2):
            for k in range(2):
                a[i][j] += (x[i][k] * y[k][j])%mod
    return a
def quick_mm_yu(M,N,mod):
    E = [[1,0],[0,1]]
    while N:
        if N%2 !=0:
            E = mm_yu(E,M,mod)
        M = mm_yu(M,M,mod)
        N >>=1
    return E
def fibonacci_yu(M,n,mod):
    f = [[1,0],[1,0]]
    return mm_yu(quick_mm_yu(M,n-2,mod),f,mod)[0][0]%mod
def mm(x,y):
    a =[[0,0],[0,0]]
    for i in range(2):
        for j in range(2):
            for k in range(2):
                a[i][j] += x[i][k] * y[k][j]
    return a
def quick_mm(M,N):
    E = [[1,0],[0,1]]
    while N:
        if N%2 !=0:
            E = mm(E,M)
        M = mm(M,M)
        N >>=1
    return E
def fibonacci(M,n):
    f = [[1,0],[1,0]]
    return mm(quick_mm(M,n-2),f)[0][0]
n,m,p = map(int,input().split())
M = [[1,1],[1,0]]
if m>n+2 :
    print(fibonacci_yu(M,n+2,p)%p-1)
else:
    mod = fibonacci(M,m)
    print(fibonacci_yu(M,n+2,mod)%mod%p-1)

参考：
https://blog.dotcpp.com/a/99877
https://blog.csdn.net/flyfish1986/article/details/48014523