[Python] 백준 10830 행렬 제곱

백준  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제곱한 결과를 출력한다.

---

제출

n,b=map(int,input().split())
l=[list(map(int, input().split())) for _ in range(n)]
def mul(l1,l2):
    res=[[0]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                res[i][j]+=l1[i][k]*l2[k][j]%1000
    return res
def p(a,b):
    if b == 1:
        return a
    else:
        t=p(a,b//2)
        if b % 2 == 0:
            return mul(t,t)
        else:
            return mul(mul(t,t),a)
r=p(l,b)
for i in r:
    for j in i:
        print(j%1000,end=" ")
    print()

예제

2 5
1 2
3 4

 

3 3
1 2 3
4 5 6
7 8 9

 

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

결과

백준 10830 행렬 제곱

 

변화하던 교육과정 속 행렬을 배우지 못한 나(응애/23)는 웁니다,

10830번: 행렬 제곱