소스코드
import sys
input = sys.stdin.readline
N,B = map(int, input().strip().split())
matrix = []
for _ in range(N):
matrix.append(list(map(int, input().strip().split())))
# 두 행렬의 곱을 수행하는 함수
def multiply_matrix(matrix_a, matrix_b):
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] += matrix_a[i][k] * matrix_b[k][j]
result[i][j] %= 1000 # 요구사항에 맞게 나머지 연산
# 행렬곱한 행렬 반환
return result
def recursive_hyper_exp(matrix, b):
# 기저조건 : 각 원소들을 모듈러 연산한 행렬
if b == 1:
return [[element % 1000 for element in row] for row in matrix]
half = recursive_hyper_exp(matrix, b // 2)
if b % 2 == 0:
return multiply_matrix(half, half)
else:
return multiply_matrix(matrix, multiply_matrix(half, half))
# 결과 출력
result = recursive_hyper_exp(matrix, B)
for i in range(N):
print(' '.join(map(str, result[i])))
Python
복사
풀이
•
곱셈 의 상위 문제라고 생각하면 좋을 것 같습니다. 거듭제곱법을 이용한 곱셈 문제에서 더 나아가 행렬 곱만 알맞게 해주면 됩니다.•
다만 약간 주의할 부분들은 다음과 같습니다 :
◦
행렬 곱을 할 때는 삼중 연산이 필요하다는 점
◦
기저조건에서 단순히 행렬을 그대로 반환하는게 아니라 모듈러 연산을 적용한 버전의 행렬로 반환해야한다는 점
•
각 행을 순회하며 띄워쓰기로 join에 출력하면 끝!