✅ BOJ 10830 - 행렬 제곱

행렬 제곱 (백준 10830)

N×N 정수 행렬 A와 정수 B가 주어짐. A를 B번 곱한 결과를 출력해야 함. 단, 모든 계산은 mod 1000.

 

전략

입력 크기 작아보이지만 B는 최대 10^9라서 단순 곱셈으론 시간 초과. 분할 정복으로 제곱 처리해야 통과 가능.

그냥 A^B 구하는 문제. B가 최대 10^9라서 단순히 곱하면 시간 터짐. 무조건 분할 정복 써야 함.

핵심은 행렬 곱셈을 제대로 구현하고, b를 반으로 쪼개면서 재귀로 처리하는 것.

 

1. 행렬 곱셈은 A[i][k] * B[k][j] 누적해서 result[i][j]에 저장하는 구조.

2. 재귀에서 종료 조건 b==1일 때 mod 1000 처리된 원본 그대로 리턴해야 함. 문제에서 출력은 전부 mod 1000이라 안 하면 틀림.
3. 홀수 제곱일 때는 반으로 나눈 거 두 번 곱하고, 마지막에 한 번 더 곱해줘야 진짜 b제곱 됨. 이거 안 하면 b가 홀수일 때 결과 잘림.

4. 그리고 base case에서 리턴 안 하면 무한재귀 빠져서 RecursionError 뜬다. 말도 안 되는 실수로 시간 날리지 마라.

---

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)

# 행렬 곱셈
def mat_mul(A, B):
    n=len(A)
    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]+=A[i][k]*B[k][j]
            result[i][j]%=1000
    return result

def mat_pow(matrix,b):
    # base case
    if b==1:
        return [[x%1000 for x in row] for row in matrix]
    
    half=mat_pow(matrix,b//2)
    result=mat_mul(half,half)
    
    # 홀수 제곱일 경우 한 번 더 곱해줌
    if b%2==1:
        result=mat_mul(result,matrix)
    
    return result

def main():
   n,b=map(int,input().split())
   matrix=[list(map(int,input().split())) for _ in range(n)]
   result=mat_pow(matrix,b)
   for row in result:
       print(*row)
    
if __name__=="__main__":
    main()