[Divide&Conquer] 백준 행렬제곱 10830 python3 풀이

https://www.acmicpc.net/problem/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제곱한 결과를 출력한다.

 

 

import sys
import copy

# N, B = map(int, sys.stdin.readline().split())
# datas = [list(map(int, sys.stdin.readline().split())) for i in range(N)]
In [2]:
N, B = 2, 5
datas = [
    [1,2],
    [3,4]
]
N, B = 3, 3
datas = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
# N, B = 5, 10
# datas = [
#     [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]
# ]
# N, B = 5, 10000
# datas = [
#     [1, 0, 0, 0, 0],
#     [0, 1, 0, 0, 0],
#     [0, 0, 1, 0, 0],
#     [0, 0, 0, 1, 0],
#     [0, 0, 0, 0, 1]
# ]
# datas = [
#     [999, 999, 999, 999, 999],
#     [999, 999, 999, 999, 999],
#     [999, 999, 999, 999, 999],
#     [999, 999, 999, 999, 999],
#     [999, 999, 999, 999, 999]
# ]
memos = {}
totals = copy.deepcopy(datas)
equals = [[1 if i == j else 0 for i in range(N)] for j in range(N)]
memos = {0: equals, 1:datas}
def mulAB(A, B): 
    global N
    result = [[0 for i in range(N)] for i in range(N)]
    for i in range(N):
        for j in range(N):
            val = 0
            for k in range(N):
                val = (val + ((A[i][k]%1000) * (B[k][j]%1000)))%1000
            result[i][j] = val
    return result
            
def process(key):
    global memos
    if (key in memos.keys()):
        return memos[key]
    q = int(key/2)
    result = mulAB(process(q), process(key - q)) 
    memos[key] = result
    return result

for i in range(N):
    print(' '.join(map(lambda a: str(a%1000), process(B)[i])))