백준 10830번: 행렬 제곱 [python]

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

문제 접근

행렬의 거듭제곱 문제와 자연수의 거듭제곱을 분할정복으로 푼것을 활용하여 푼다.

A^k일 때

k가 홀수이면, A^(k//2) A^(k//2) A 로 분할

k가 짝수이면, A^(k//2) * A(k//2) 로 분할

행렬의 곱셈은 연산하는 함수를 따로 정의 해준다.

import sys
input = sys.stdin.readline

# N: 행렬 크기, exponent: 거듭제곱할 횟수
N, exponent = map(int, input().split())

# 입력 행렬 저장
matrix = [list(map(int, input().split())) for _ in range(N)]

# 행렬 곱셈 함수
def multiply_matrices(mat1, mat2):
    size = len(mat1)
    result = [[0] * size for _ in range(size)]

    # 기본적인 행렬 곱셈 구현
    for row in range(size):
        for col in range(size):
            cell_sum = 0
            for k in range(size):
                cell_sum += mat1[row][k] * mat2[k][col]
            result[row][col] = cell_sum % 1000  # 문제 조건: 1000으로 나눈 나머지만 저장

    return result

# 분할 정복을 이용한 행렬 거듭제곱
def matrix_power(matrix, power):
    # 종료 조건: 행렬의 1제곱일 때는 각 원소를 1000으로 나눈 값 반환
    if power == 1:
        return [[element % 1000 for element in row] for row in matrix]
    
    # 재귀적으로 절반 제곱 계산
    half = matrix_power(matrix, power // 2)
    half_squared = multiply_matrices(half, half)

    # 홀수 제곱일 경우 한 번 더 곱해줌
    if power % 2 == 1:
        return multiply_matrices(half_squared, matrix)
    else:
        return half_squared

# 결과 계산
result = matrix_power(matrix, exponent)

# 결과 출력
for row in result:
    print(*row)