f1 = 0, f2 = 1 이라면, 0, 1, 1, 2, 3, 5... 일 것이다.
[f1, f2] = [0, 1]이다.
[f2, f3] = A[0, 1]이다.
A를 구하는 것은 원래의 점화식을 생각하면 쉽다.
[
1 0
1 1
]
이다.
그렇다면,
[f3, f4] = A[f2, f3]인데,
[f2, f3]은 풀어서 보면 A*[0,1]이다.
따라서, 결합 법칙과 일반화를 통해 A^n[0,1]을 [fn, fn+1]으로 볼 수 있다.
문제풀기 위해 시간복잡도를 줄이면, A^n은 A^(n/2)의 제곱으로 처리가 가능하다.
그래서 O(logN)이 된다.
