蓝桥杯基础练习VIP-矩阵乘法 快速幂

解题思路:

快速幂

注意事项:

参考代码:

from functools import reduce

#矩阵乘法

def MatrixMul(MatrixA,MatrixB):

    tempMatrix =[ [0]*len(MatrixB[0]) for i in range(len(MatrixA))]

    for i in range(len(MatrixA)):

        for j in range(len(MatrixB[0])):

            for k in range(len(MatrixA[0])):

                tempMatrix[i][j] +=MatrixA[i][k]*MatrixB[k][j]

    return tempMatrix

def QuickMul(Matrix,n):

    res = list(map(lambda x:list(map(int,x)),[[ i==j for j in range(len(Matrix[0]))] for i in range(len(Matrix))]))#获得单位矩阵

    while n:

        if n&1:#末尾为1

            res = MatrixMul(res,Matrix)

        n >>= 1

        Matrix = MatrixMul(Matrix,Matrix)

    return res

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

Matrix = list()

for i in range(m):

    Matrix.append(list(map(int,input().split())))

Matrix = QuickMul(Matrix,n)

for i in range(len(Matrix)):

    print(" ".join(list(map(str,Matrix[i]))))