10830. 행렬 제곱

업데이트 시간 : 2023-02-02 07:58:05 +0000

[Gold IV] 행렬 제곱 - 10830

문제 링크

성능 요약

메모리: 114328 KB, 시간: 136 ms

분류

분할 정복(divide_and_conquer), 분할 정복을 이용한 거듭제곱(exponentiation_by_squaring), 선형대수학(linear_algebra), 수학(math)

문제 설명

크기가 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제곱한 결과를 출력한다.

💡 Solutions

📄 행렬 제곱.py

import sys

N, B = map(int,sys.stdin.readline().split())
A = [list(map(int,sys.stdin.readline().split())) for _ in range(N)]

def pw_m(m1 : list, m2 : list):
  result = [[0]*N for _ in range(N)]
  for i in range(N):
    for j in range(N):
      for k in range(N):
        result[i][j] += (m1[i][k] * m2[k][j])%1000
  return result

def dac(num : int ,matrix : list):
  if num == 1: return matrix
  mat = dac(num // 2, matrix)
  return pw_m(mat, mat) if num%2 ==0 else pw_m(pw_m(mat, mat),matrix)

ans = dac(B, A)
for row in ans : 
  for col in row:
    print(col%1000,end=" ")
  print()