[백준 - 11444] 피보나치 수 6

n이 매우 커서 앞에서부터 피보나치 수를 더하는 방식은 사용할 수 없다. 피보나치 점화식은 아래 행렬의 거듭제곱으로 표현할 수 있다.

|1 1|^n
|1 0|

이 행렬의 원소에는 F(n+1), F(n)이 들어간다. 그래서 지수를 절반으로 나누며 행렬을 제곱했다.

• 지수가 짝수면 A^(n/2)를 구한 뒤 제곱한다.
• 지수가 홀수면 제곱한 뒤 기준 행렬을 한 번 더 곱한다.

재귀 깊이는 n이 아니라 log n이 된다. 모든 행렬 곱셈에서 바로 나머지를 적용해 값이 커지는 것도 막았다.

문제: 11444 피보나치 수 6 · 코드: GitHub에서 보기