[C++] 백준 10830 - 행렬 제곱

🔐 백준 10830 - 행렬 제곱

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

🔑 풀이

B가 최대 $ 10^{11} $ 으로 매우 크다. 따라서 단순히 행렬 곱셈을 B번 반복하면 계산량이

기하급수적으로 증가한다. 따라서 효율적인 계산을 수행해야 한다.

이를 위한 해결 방법으로 거듭 제곱을 분할 정복을 이용해서 수행하는 방법이 있다.

• $ A^B = (A^{B/2}) × (A^{B/2}) $ (B가 짝수일 때)

• $ A^B = (A^{B-1}) × A $ (B가 홀수일 때)

이를 이용하면 거듭제곱 연산을 줄일 수 있다.

행렬 곱셈을 수행하면서 계산 도중 각 결과를 1,000으로 나눈 나머지를 유지하여 오버플로우를 방지한다.

🧩 코드