백준 10830번 행렬 제곱

정보

문제 바로가기 [클릭]

난이도: Gold4

관련 개념: #수학 #분할 정복 #분할 정복을 이용한 거듭제곱 #선형대수학

---

조건

시간 제한	메모리 제한
1 초	256 MB

---

문제

크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.

---

입력

첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤ 5, 1 ≤ B ≤ 100,000,000,000)

둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다.

---

출력

첫째 줄부터 N개의 줄에 걸쳐 행렬 A를 B제곱한 결과를 출력한다.

---

예제 입출력 1

입력

2 5
1 2
3 4

출력

69 558
337 406

---

예제 입출력 2

입력

3 3
1 2 3
4 5 6
7 8 9

출력

468 576 684
62 305 548
656 34 412

---

예제 입출력 3

입력

5 10
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1

출력

512 0 0 0 512
512 0 0 0 512
512 0 0 0 512
512 0 0 0 512
512 0 0 0 512

---

코드(파이썬)

def daq(b):
    if b in memo:
        return memo[b]
    else:
        tmp1 = daq(b//2)
        tmp2 = daq(b//2 + 1) if b%2 else memo[b//2] 
    
        r = [[0] * N for _ in range(N)]
        for x in range(N):
            for y in range(N):
                r[x][y] = sum([a*b for a, b in zip(tmp1[x], [tmp2[i][y] for i in range(N)])]) % 1000
        memo[b] = r
        
        return r

N, B = map(int, input().split())
arr = [list(map(lambda x:int(x) % 1000, input().split())) for _ in range(N)]
memo = {1:arr}

for line in daq(B):
    print(*line)

---

특이사항

• 입력, 출력조건을 명확하게 확인할 필요가 있음

---

참고문헌

-