[백준] 10830번 행렬제곱

출처: [백준] 2740번 행렬곱셈

---

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	10162	3490	2817	34.179%

---

문제

크기가 N x 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

예제 출력 1

69 558
337 406

예제 입력 2

3 3
1 2 3
4 5 6
7 8 9

예제 출력 2

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

예제 출력 3

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

---

힌트

• -

---

출처

• 문제를 만든 사람: baekjoon
• 데이터를 추가한 사람: doju
• 잘못된 조건을 찾은 사람: dreammusic23

---

알고리즘 분류

• 수학
• 분할 정복
• 분할 정복을 이용한 거듭제곱
• 선형대수학

---

시간 제한

• -

---

풀이

• -

---

소스코드

import sys

input = sys.stdin.readline

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


def matrix_multiple(a, b):
    if b == 1:
        for i in range(N):
            for j in range(N):
                a[i][j] %= 1000
        return a
    else:
        if b % 2 == 0:  # 제곱수가 짝수일 때 AAAAAA --> (A^2)^2^2
            temp_matrix = [[0 for _ in range(N)] for _ in range(N)]
            c = matrix_multiple(a, b // 2)
            for i in range(N):
                for j in range(N):
                    for k in range(N):
                        temp_matrix[i][j] += c[i][k] * c[k][j]
                    temp_matrix[i][j] %= 1000
            return temp_matrix

        else:  # AAAAA --> (A^2)^2 * A
            temp_matrix = [[0 for _ in range(N)] for _ in range(N)]
            c = matrix_multiple(a, b - 1)
            for i in range(N):
                for j in range(N):
                    for k in range(N):
                        temp_matrix[i][j] += c[i][k] * a[k][j]
                    temp_matrix[i][j] %= 1000
            return temp_matrix


result = matrix_multiple(matrix, B)
for row in result:
    for value in row:
        print(value, end=" ")
    print()