[BOJ][python] 10830. 행렬 제곱

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

10830번: 행렬 제곱

---

💡IDEA

분할 정복을 사용하는 문제이다.

문제를 처음 보았을 때, 배열 안의 각 숫자를 제곱하면 되는 건 줄 알았지만 그게 아니라 행렬 자체를 제곱하는 문제였다.

선형대수학에서 행렬의 곱셈을 알아햐 하는데, 공식은 다음과 같다.

행렬 곱 공식

A 행렬 × B 행렬 을 계산하기 위해서 A 행렬의 열과 B 행렬의 행의 각 수들을 곱해서 더한다.

operator 라이브러리의 matmul 라는 행렬 곱셈 함수를 사용할 수 있겠지만, 이 문제는 각 수가 너무 커질 것을 방지하여 1000으로 나눈 나머지로 업데이트 해주어야 하기 때문에 따로 함수를 만들어 주었다.

또한 1629번을 풀어보았다면 이 문제를 쉽게 생각해 볼 수 있다.

지수법칙 A^(m+n) = A^m × A^n 과 나머지 분배 법칙 (A×B)%C = (A%C) × (B%C) % C 을 알 면 된다.

 

예를 들어, 5^10 % 1000 을 생각해보자.

5^10 % 1000

= ((5^5 % 1000) × (5^5 % 1000)) % 1000

= ((5^2 % 1000 × 5^2 % 1000 × 5) % 1000 × (5^2 % 1000 × 5^2 % 1000 × 5) % 1000) % 1000

 

A^B % 1000 를 위와 같은 방식으로 B를 반씩 분할해가면서, B가 홀수인지 짝수인지 경우에 따라 계산한다.

 

📌CODE

import sys
input = sys.stdin.readline

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

def matmul(a, b):
    mul = [[0]*N for _ in range(N)]
    for r in range(N):
        for c in range(N):
            tmp = 0
            for i in range(N):
                tmp += a[r][i] * b[i][c]
            mul[r][c] = tmp%1000
    return mul

def solve(a, b):
    if b == 1:
        for r in range(N):
            for c in range(N):
                a[r][c] %= 1000
        return a
    tmp = solve(a, b//2)
    if b%2:
        return matmul(matmul(tmp, tmp), a)
    else:
        return matmul(tmp, tmp)

for row in solve(A, B):
    print(*row)