python代码

def matmul(m1, m2, mod):
    rows1 = len(m1)
    cols1 = len(m1[0])
    cols2 = len(m2[0])
    res = [[0] * cols2 for _ in range(rows1)]
    for i in range(rows1):
        for j in range(cols2):
            for k in range(cols1):
                res[i][j] = (res[i][j] + m1[i][k] * m2[k][j]) % mod
    return res

def addmat(m1, m2, mod):
    n = len(m1)
    res = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            res[i][j] = (m1[i][j] + m2[i][j]) % mod
    return res

def matrix_power(matrix, k, mod):
    n = len(matrix)
    res = [[1 if i == j else 0 for j in range(n)] for i in range(n)]
    while k > 0:
        if k % 2 == 1:
            res = matmul(res, matrix, mod)
        matrix = matmul(matrix, matrix, mod)
        k //= 2
    return res

def calculate_sum(matrix, k, mod):
    n = len(matrix)
    if k == 1:
        return matrix
    half_k = k // 2
    half_sum = calculate_sum(matrix, half_k, mod)
    half_power = matrix_power(matrix, half_k, mod)
    if k % 2 == 0:
        return addmat(half_sum, matmul(half_power, half_sum, mod), mod)
    else:
        return addmat(matrix, addmat(matmul(matrix, half_sum, mod), matmul(matrix, matmul(half_power, half_sum, mod), mod), mod), mod)

if __name__ == '__main__':
    n, k, m1 = map(int, input().split())
    m = []
    for i in range(n):
        m.append(list(map(int, input().split())))
    b = calculate_sum(m, k, m1)
    for i in range(n):
        for j in range(n):
            print(b[i][j], end=' ')
        print()