[백준 - 2086] 피보나치 수의 합

피보나치 구간합을 두 항의 차로 바꾸고 행렬 거듭제곱으로 계산한 풀이.

2022년 9월 1일

a번째부터 b번째 피보나치 수의 합을 그대로 더하면 범위가 너무 크다. 피보나치 수열에는 아래 관계가 있다.

F(1) + F(2) + ... + F(n) = F(n + 2) - 1

그래서 구간합은 F(b + 2) - F(a + 1)로 바꿀 수 있다. 필요한 두 피보나치 수는 2×2 행렬의 빠른 거듭제곱으로 구했다.

마지막 아홉 자리만 필요하므로, 뺄셈 결과가 음수가 되는 경우에는 모듈러 값을 더해 보정했다. 큰 범위의 합을 점화식의 항 두 개로 줄인 것이 핵심이다.