[백준 - 2749] 피보나치 수 3

피보나치 수 6과 같은 행렬 거듭제곱 구조를 사용하되, 이 문제는 1,000,000으로 나눈 나머지를 구한다.

Q = |1 1|
    |1 0|

Q^(n - 1)의 왼쪽 위 원소 = F(n)

지수를 절반으로 나누며 현재 행렬을 제곱하고, 홀수 지수에서는 기준 행렬을 한 번 더 곱했다. 행렬 원소 네 개만 관리하면서 모든 곱셈마다 모듈러 연산을 적용했다.

문제: 2749 피보나치 수 3 · 코드: GitHub에서 보기