[Python]분할정복 백준 10830

   문제

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

분할정복으로 제곱을 구현했던것과 같다.

(A)^8을 계산하는데 8번(N번) 계산해야한다면

(A^2)^2)^2로 구할시 3번(logN번)만에 계산할수있다.

import sys
N,B=map(int,sys.stdin.readline().split())
A=[list(map(int,sys.stdin.readline().split())) for _ in range(N)]
 
 
def matric_mul(A,B):
    if B==1:
        for i in range(N):
            for j in range(N):
                A[i][j]%=1000
        return A
 
    elif B%2==1:
        tmp=[[0 for _ in range(N)] for _ in range(N)]
        C=matric_mul(A,B-1)
        for i in range(N):
            for j in range(N):
                for k in range(N):
                    tmp[i][j]+=C[i][k]*A[k][j]
                tmp[i][j]%=1000
 
        return tmp
 
    else:
        tmp=[[0 for _ in range(N)] for _ in range(N)]
        C=matric_mul(A,B//2)
        for i in range(N):
            for j in range(N):
                for k in range(N):
                    tmp[i][j]+=C[i][k]*C[k][j]
                tmp[i][j]%=1000
        return tmp
 
result=matric_mul(A,B)
for li in result:
    for p in li:
        print(p,end=' ')
    print()