백준 10830 - 행렬 제곱 (파이썬)

Answer

def mul(a, b):
    tmp = [[0 for _ in range(N)] for _ in range(N)]

    for i in range(N):
        for j in range(N):
            for k in range(N):
                tmp[i][j] += a[i][k] * b[k][j]
    
    return remainder(tmp)

def power(b, m):
    if b == 1:
        return remainder(m)
    else:
        tmp = power(b // 2, m)
        if b % 2 == 0:
            return mul(tmp, tmp)
        else:
            return mul(mul(tmp, tmp), m)

def remainder(m):
    for i in range(N):
        for j in range(N):
            m[i][j] %= 1000

    return m

N, B = map(int, input().split())
M = [list(map(int, input().split())) for _ in range(N)]
answer = power(B, M)

for i in answer:
    print(*i)