[백준 10830] 행렬 제곱

문제 

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

10830번: 행렬 제곱

---

아이디어

https://park-mingyu.tistory.com/38

[백준 1629] 곱셈

이 문제랑 똑같다. 아주 똑같다. 그런데 단 한 가지가 다르다면 행렬 곱 연산을 구현해야 한다는 것 정도,,?

행렬 A의 B제곱을 구하라는데 B의 범위가 1 ≤ B ≤ 100,000,000,000 이다.

(1629번 문제를 안 풀고 이걸 봤으면 어안이 벙벙했을 듯.  하지만 어안이 벙벙하지 않았기 때문에 1629번 문제를 풀었다는 게 증명이 된다.)

 

먼저, matmul 함수를 통해 두 행렬의 곱을 구현해준다.

 

그리고, rem 함수를 통해서 행렬의 각 원소에 대해서 1000으로 나눈 나머지를 구해주는 연산을 수행한다. 

 

마지막으로, f 함수를 통해서 분할 정복을 통한 거듭제곱을 구현해준다.

---

Solution

n, b = map(int, input().split()) 

def matmul(mat1, mat2) :
    l = len(mat1) 
    res = [[0 for _ in range(l)] for _ in range(l)]
    
    for i in range(l) : 
        for j in range(l) :
            f = mat1[i] 
            b = [m[j] for m in mat2] 
            res[i][j] = sum([x*y for x,y in zip(f, b)])
            
    return res

def rem(mat) : 
    l = len(mat) 

    for i in range(l) : 
        for j in range(l) : 
            mat[i][j] %= 1000
    return mat
    
def f(a, b) :
    if b == 1 : 
        return rem(a) 

    else : 
        rec = f(a, b//2) 
        if b % 2 == 0 : 
            return rem(matmul(rec, rec))
        
        else : 
            return rem(matmul(matmul(rec, rec), a))

lst = [] 
for _ in range(n) : 
    lst.append(list(map(int, input().split())))

answer = f(lst, b)

for a in (answer) : 
    print(' '.join([str(x) for x in a]))