10830.md

백준 10830번 행렬 재곱

https://www.acmicpc.net/problem/10830

---

소스코드

• 메모리 : 30864 KB
• 시간 : 68 ms

def solution(x,y):
    if y == 1:
        for i in range(n):
            for j in range(n):
                x[i][j]%=1000
        return x
 
    elif y%2 == 1:
        temp = [[0 for i in range(n)] for j in range(n)]
        z = solution(x,y-1)
        for i in range(n):
            for j in range(n):
                for k in range(n):
                    temp[i][j] += z[i][k] * x[k][j]
                temp[i][j] %= 1000
 
        return temp
 
    else:
        temp = [[0 for i in range(n)] for j in range(n)]
        z = solution(x,y//2)
        for i in range(n):
            for j in range(n):
                for k in range(n):
                    temp[i][j] += z[i][k] * z[k][j]
                temp[i][j]%=1000
        return temp

n, b = map(int,input().split())
matrix = [list(map(int,input().split())) for i in range(n)]
 
answer = solution(matrix,b)

for a in answer:
    for aa in a:
        print(aa,end=' ')
    print()