[골드 4] 백준 10830 - 행렬 제곱 (파이썬)

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

풀이

• 크기 N \times N의 정수 행렬 A가 주어짐
• 자연수 B가 주어질 때,
• A^B \mod 1000 을 구하라
• (여기서 A^B는 행렬 곱 기준의 거듭제곱)

내가 먼저 실수한 부분은 다음과 같다.

• A ** B → 원소별 제곱임 (X)
• for i in range(B): A = A @ A → 시간 초과 (X)

풀이 순서를 생각하면 다음과 같다.

1. 팩토리얼 전처리
   • 0!부터 N!까지 전부 리스트에 저장 (O(N))
2. 분자 계산
   • N!
3. 분모 계산
   • K! * (N-K)!
4. 모듈러 역원 적용
   • 분모의 역원을 구해서 분자와 곱함
5. 최종 계산
   • 결과를 MOD로 나눈다

✅ 정답 접근 (분할 정복)

🔍 핵심 아이디어

• \( A^B = A^{B//2} \times A^{B//2} \) (짝수)
• \( A^B = A^{B//2} \times A^{B//2} \times A \) (홀수)
• 각 곱셈 이후에는 mod 1000 연산 적용

코드

# 백준 10830 - 행렬 제곱
# 분류 : 수학
# 문제집 : 단기간 성장 - 5번

import numpy as np

N, B = map(int, input().split())
A = np.array([list(map(int, input().split())) for _ in range(N)])

def matrix_pow(A, B) :
    if B == 1 :
        return A % 1000
    half = matrix_pow(A, B // 2)
    half_squared = np.matmul(half, half) % 1000

    if B % 2 == 0 :
        return half_squared
    else :
        return np.matmul(half_squared, A) % 1000

result = matrix_pow(A, B)
for row in result :
    print(*row)