蓝桥杯算法提高VIP-矩阵乘方-题解（Python代码）矩阵快速幂

解题思路:

注意事项:

参考代码:

def mulMatrix(x,y):
        c=[[0 for i in range(2)] for i in range(2)]
        for i in range(2):
                for j in range(2):
                        for k in range(2):
                                c[i][j]+=x[i][k]*y[k][j]
                                c[i][j]%=m
        return c
def fastMatrixPower(matrix,power):
        res=[[0 for i in range(2)] for i in range(2)]
        for i in range(2):
                res[i][i]=1
        while power:
                if power & 1:
                        res=mulMatrix(matrix,res)
                matrix=mulMatrix(matrix,matrix)
                power>>=1
        return res
b,m=map(int,input().split())
mar=[]
for i in range(2):
        mar.append(list(map(int,input().split())))
if b==0:
        mar0=[[1,0],[0,1]]
        for i,j in mar0:
                print(i%m,j%m)

else:
        re=fastMatrixPower(mar,b)
        for i,j in re:
                print(i%m,j%m)