by Jerry Sky
2020-03-09
[1110]n=[Fn+1FnFnFn−1] \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} F_{n+1} & F_n\\ F_{n} & F_{n-1} \end{bmatrix} [1110]n=[Fn+1FnFnFn−1]
→O(logn)\rightarrow O(\log n)→O(logn)