[BOJ] 10830번 행렬 제곱

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

제곱수를 분할정복을 통해 빠르게 구하는 로직을 행렬에 적용하는 문제이다.
일반 자연수의 풀이를 행렬 개념에 적용하여 풀이했다.

M = 1000  # 모듈로에 쓰일 값

# 행렬 모든 원소에 모듈로 연산
def matrix_modulo(matrix):
    matrix_size = len(matrix)
    for i in range(matrix_size):
        for j in range(matrix_size):
            matrix[i][j] = matrix[i][j] % M
    return matrix

# 행렬 곱
def matrix_multiply(matrix1, matrix2):
    matrix_size = len(matrix1)  # 문제조건에서 최대 5
    new_matrix = [[0] * matrix_size for _ in range(matrix_size)]
    for i in range(matrix_size):
        for j in range(matrix_size):
            for k in range(matrix_size):
                new_matrix[i][j] += matrix1[i][k] * matrix2[k][j]
    return matrix_modulo(new_matrix)


# (matrix^n) mod m 반환
def matrix_pow(matrix, n):
    if n == 1:
        return matrix_modulo(matrix)

    if n % 2 == 0:  # 제곱수가 짝수일 때
        half_matrix = matrix_pow(matrix, n//2)
        return matrix_multiply(half_matrix, half_matrix)
    else:
        half_matrix = matrix_pow(matrix, (n-1)//2)
        return matrix_multiply(matrix_multiply(half_matrix, half_matrix), matrix)

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

ans_matrix = matrix_pow(matrix, B)
for row in ans_matrix:
  print(*row)