[백준] 10830번 행렬 제곱 [Python]

 

 

NxN 행렬 A의 B 제곱을 구하는 문제

각 원소를 1,000으로 나눈 나머지를 출력

 

문제

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

입력

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

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

출력

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

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

 

아래 규칙으로 홀/짝에 대해서 분할 정복

$A=A$

$A^2=A\ast A$

$A^3=A\ast A^2$

 

$A^{2n}=A^n\ast A^n$
$A^{2n+1}=A\ast A^n\ast A^n$

 

행렬 곱은 앞 행렬의 행과 뒷 행렬의 열을 각각 곱하고 모듈러 연산하고 합산하도록 구현했습니다.

import sys
input = sys.stdin.readline

N, B = map(int, input().split())
A = []
for _ in range(N):
    A.append([n%1000 for n in map(int, input().split())])

def mul(a, b):
    return [[sum(i*j%1000 for i, j in zip(ar, br))%1000 for br in zip(*b)] for ar in a]

def bi(a, x):
    if x == 1:
        return a
    if x%2:
        k = bi(a,x//2)
        return mul(a, mul(k, k))
    else:
        k = bi(a,x//2)
        return mul(k, k)

print("\n".join(" ".join(map(str, row)) for row in bi(A, B)))

 

 

예제 입력 1 

2 5
1 2
3 4

예제 출력 1 

69 558
337 406

예제 입력 2 

3 3
1 2 3
4 5 6
7 8 9

예제 출력 2 

468 576 684
62 305 548
656 34 412

예제 입력 3 

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

예제 출력 3 

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