矩阵快速幂-python（最后一个运行超时）

解题思路:

注意事项:

参考代码:

n,m,p = map(int,input().split())

# 定义快速幂,k为取模的时候使用

def fp(base, power:int, k=float('inf')):

    res = 1 

    while power>0:

        if power&1:

            res *= base%k

        power >>= 1 

        base *= base%k

    return res

# 矩阵点乘    

def matrix_m(n,m):

    R = [[0]*len(m[0]) for i in range(len(n))]

    for a in range(len(n)):

        for b in range(len(m[0])):

            total = 0

            for c in range(len(n[0])):

                total += n[a][c]*m[c][b]

            R[a][b] = total

    return R  

# 矩阵快速幂

def m_fp(base,power):

    def get(n,i):

        v = [0]*n 

        v[i] = 1 

        return v 

    res = [get(len(base),i) for i in range(len(base))]

    while power>0:

        if power&1:

            res = matrix_m(res,base)

        power >>= 1 

        base = matrix_m(base,base)

    return res

T = [[1,1],[1,0]]

f_m = matrix_m(m_fp(T,m-2),[[1],[1]])[0][0]

s_n = matrix_m(m_fp(T,n),[[1],[1]])[0][0]-1

#print(f_m,s_n)

print(s_n%f_m%p)