[분할 정복] 백준 10830번: 행렬 제곱

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

10830번: 행렬 제곱

import collections

n, b = map(int, input().split())

a = []
for i in range(n):
    a.append(list(map(int, input().split())))

dct = collections.defaultdict(list)
dct[1] = a

def cross(m1, m2, n1, n2):
    result = [[0 for _ in range(n)] for _ in range(n)]

    converted = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            converted[i][j] = m2[j][i]

    for i in range(n):
        for j in range(n):
            row = m1[i]
            col = converted[j]
            num = 0
            for k in range(n):
                num += row[k]*col[k]
            result[i][j] = num%1000
    dct[n1+n2] = result
    return result


cross(a, a, 1, 1)

def divide_and_conquer(num):
    if dct[num] != []:
        return dct[num]

    if num == 2:
        return dct[2]

    if num == 1:
        return dct[1]

    n1 = num//2
    n2 = num - n1

    mat1 = divide_and_conquer(n1)
    mat2 = divide_and_conquer(n2)

    return cross(mat1, mat2, n1, n2)


answer = divide_and_conquer(b)

for i in range(n):
    row = []
    for j in range(n):
        row.append(answer[i][j]%1000)
    print(*row)

 

주목할 점은 b의 최댓값이 1000억이다.

행렬을 1000억번 제곱한다? 이걸 이대로 풀면 당연히 시간초과가 난다. 그래서 분할 정복을  사용했다.

a의 1000억제곱 = a의 500억제곱 * a의 500억제곱이니까

분할 정복에서도 숫자를 절반씩 나눠가면서 제곱값을 구해나간다.

 

각 성분의 숫자들은 1000이 넘어가면 1000으로 나눠준다. 어차피 결과도 1000으로 나눈 나머지를 내는거니깐!