170. 10830(행렬 제곱) - 파이썬

import sys
input = sys.stdin.readline


# 행렬 곱을 처리하는 부분

def MatrixMul(A, B):
    N = len(A)
    C = [[0 for _ in range(N)] for _ in range(N)]

    for i in range(N):
        for j in range(N):
            for k in range(N):
                C[i][j] += A[i][k] * B[k][j]

    remainder(C)
    return C

# 1000으로 나눈 나머지를 구하는 부분


def remainder(A):
    N = len(A)
    for i in range(N):
        for j in range(N):
            A[i][j] %= 1000

# 거듭 제곱을 분할정복으로 하는 부분


def pow(A, B):
    if B == 1:
        return A

    tmp = pow(A, B//2)

    if B % 2 == 1:
        return MatrixMul(MatrixMul(tmp, tmp), A)
    else:
        return MatrixMul(tmp, tmp)


N, B = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
remainder(A)  # 들어온 값들이 1000보다 클 수 있므로 나눔.

result = pow(A, B)
for val in result:
    print(*val)

문제요약

행렬 곱을 진행하라(분할정복을 이용해서)

설명

먼저 행렬의 곱셈은 다음으로 나타낼 수 있다.

제곱은 다음으로 나타낼 수 있다.

따라서 행렬의 곱셈은 

def MatrixMul(A, B):
    N = len(A)
    C = [[0 for _ in range(N)] for _ in range(N)]

    for i in range(N):
        for j in range(N):
            for k in range(N):
                C[i][j] += A[i][k] * B[k][j]

    remainder(C)
    return C

위와 같이 표현했다.

 

remailder는 1000의 나머지를 구하기 위해 사용해 준 것이다.

때문에 다음과 같이 나타낼 수 있다.

def remainder(A):
    N = len(A)
    for i in range(N):
        for j in range(N):
            A[i][j] %= 1000

 

거듭제곱 또한 위에서 나타낸거 같이

def pow(A, B):
    if B == 1:
        return A

    tmp = pow(A, B//2)

    if B % 2 == 1:
        return MatrixMul(MatrixMul(tmp, tmp), A)
    else:
        return MatrixMul(tmp, tmp)

이런식으로 코드를 짤 수 있고, 분할 정복 단계에서 거듭제곱은 많이 다뤘기 때문에 이해는데 어렵지 않을 것이다.

 

※입력이 1000보다 클 수 있다.

따라서 먼저 remainder를 실행하고 계산을 진행 하는 것이 좋다.

remainder(A)  # 들어온 값들이 1000보다 클 수 있므로 나눔.