다시 한 번 모듈러 연산 with BOJ 10830(행렬 제곱)

1. 들어가며

오늘 푼 알고리즘 문제에서 또 다시 모듈러 연산이 활용되어 정리하고자 글을 쓴다.

---

2. 모듈러 연산의 곱셈 성질

문제에서 사용된 이론은 바로 모듈러 연산의 곱셈 성질이다. 내용은 아래와 같다.

• 곱셈 성질(the multiplication property of modular arithmetic)
  - (A * B) mod C = (A mod C * B mod C) mod C

---

3. 문제 풀이: BOJ 10830(행렬 제곱)

✅ 문제: BOJ 10830

행렬 곱을 수행할 때마다 곱셈 성질을 적용하지 않으면 나중에 숫자가 너무 커져 시간 초과가 발생한다. 따라서 행렬 곱 결과를 그대로 return 하지 않고 각 원소에 mod 1000 을 적용해주고 행렬을 return한다.

import sys
sys.stdin = open('10830_input.txt')

# 행렬곱 함수
def matmul(a, b, d=1000):
    row_len = len(a)
    col_len = len(b[0])
    result = [[0] * col_len for _ in range(row_len)]

    a_col_len = len(a[0])
    for r in range(row_len):
        for c in range(col_len):
            v = 0
            for i in range(a_col_len):
                v += a[r][i] * b[i][c]
            
            # v mod d를 결과값으로 넣어주어 추후 연산 크기를 줄여줌
            result[r][c] = v % d
    return result

# 분할정복
def div_con(a, n, e):
    # n==1일 경우 항등함수와 곱해줌
    if n == 1:
        return matmul(a, e)
    else:
        # n이 짝수일 경우
        if n % 2 == 0:
            mat = div_con(a, n//2, e)
            mat = matmul(mat, mat)
            
        # n이 홀수일 경우
        else:
            mat = div_con(a, (n-1)//2, e)
            mat = matmul(mat, mat)
            mat = matmul(mat, a)
            
    return mat

N, B = map(int, sys.stdin.readline().split())

A = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

# 항등함수 만들기
E = [[0] * len(A[0]) for _ in range(len(A))]
for i in range(len(E)):
    E[i][i] = 1

result = div_con(A, B, E)
for i in range(len(result)):
    print(' '.join(map(str, result[i])))