[ 백준 / 파이썬 ] 골드 4 - 10830. 행렬 제곱

난이도

문제

크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.

입력

첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤ 5, 1 ≤ B ≤ 100,000,000,000)

둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄부터 N개의 줄에 걸쳐 행렬 A를 B제곱한 결과를 출력한다.

예제

입력	출력
2 5 1 2 3 4	69 558 337 406

입력	출력
3 3 1 2 3 4 5 6 7 8 9	468 576 684 62 305 548 656 34 412

입력	출력
5 10 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1	512 0 0 0 512 512 0 0 0 512 512 0 0 0 512 512 0 0 0 512 512 0 0 0 512

풀이

이 문제를 푸려면 빠른 거듭제곱 알고리즘을 알아야한다.

빠른 거듭제곱 알고리즘이란 거듭제곱의 횟수를 $log_2N$ 만큼 줄일 수 있다.

예를 들어 $A^{N}$ 을 구하려고 할 때 $A$를 실제로 N번 곱해도 당연히 구할 수 있겠지만, 이 문제에서 N 의 범위가 무려 $10^{12}$ 이다.

반복문을 천억번 이상 반복하면 절대로 1초안에 연산이 끝날 수 가 없다.

그래서 빠른 거듭제곰 알고리즘을 사용해야만 풀 수 있다.

N = 33이라고 입력이 들어왔을 때, 빠른 거듭제곱 알고리즘을 사용하면 아래와 같이 풀 수 있다.

이렇게 거듭제곱의 공식을 찾을 수 있다.

즉, N이 홀수일 때 N/2 승 제곱 * A , 짝수일 때 N/2 승 제곱 이걸 N이 1이 될 때 까지 반복하면 된다.

N / 2를 반복해도 되고, N을 이진화 시켜서 앞에서부터 읽어도 된다.

코드

from sys import stdin
from copy import deepcopy

input = stdin.readline

def times(arr, target, N):

    answer = [[0 for _ in range(N)] for _ in range(N)]

    for i in range(N):
        for j in range(N):
            for k in range(N):
                answer[i][j] += (arr[i][k] % 1000 * target[k][j] % 1000) % 1000

    return answer

def solution():
    N, B = map(int, input().split())

    arr = [list(map(int, input().split())) for _ in range(N)]
    org = deepcopy(arr)

    bin_B = format(B, 'b')


    for case in range(1, len(bin_B)):
        if bin_B[case] == '1':
            arr = times(arr, arr, N)
            arr = times(arr, org, N)

        else:
            arr = times(arr, arr, N)


    for i in range(N):
        for j in range(N):
            arr[i][j] %= 1000

    for a in arr:
        print(*a)


solution()