1. 斐波那契数列
斐波那契数列的表达式为：f ( n + 1 ) = f ( n ) + f ( n − 1 ) , n ≥ 0 f(n + 1) = f(n) + f(n-1), n \ge 0f(n+1)=f(n)+f(n−1),n≥0，其中 f ( n ) f(n)f(n) 为 数列中第n nn个数， f ( 1 ) = 1 , f ( 0 ) = 1 f(1) = 1, f(0) = 1f(1)=1,f(0)=1。
2. 斐波那契数列快速幂计算第n nn个值
该方法基于以下定理， 设斐波那契数列第n nn个数为F n F_nFn, 则有：
[ F n + 1 F n ] = [ 1 1 1 0 ] n [ F 1 F 0 ] \begin{bmatrix} F_{n+1} \\ F_{n} \\ \end{bmatrix} = \begin{bmatrix} 1 & 1\\ 1 & 0 \\ \end{bmatrix}^{n} \begin{bmatrix}F_1\\ F_0\\ \end{bmatrix}[Fn+1Fn]=[1110]n[F1F0]
设:A n = [ 1 1 1 0 ] n A_n = \begin{bmatrix} 1 & 1\\ 1 & 0 \\ \end{bmatrix}^{n}An=[1110]n
则我们可以对A n A_nAn进行分治方法计算，即计算
A n = A n 2 A n 2 = A n 4 A n 4 A n 4 A n 4 = . . . . = [ 1 1 1 0 ] n A_n = A_{\frac{n}{2}}A_{\frac{n}{2}} = A_{\frac{n}{4}}A_{\frac{n}{4}}A_{\frac{n}{4}}A_{\frac{n}{4}} = .... = \begin{bmatrix} 1 & 1\\ 1 & 0 \\ \end{bmatrix}^{n}An=A2nA2n=A4nA4nA4nA4n=....=[1110]n
每一步仅需要计算其中一项，即总体使用Θ ( log n ) \Theta(\log n)Θ(logn)的计算即可完成。
另外，对于A n A_nAn, 我们有：
A n = [ F n + 1 F n F n F n − 1 ] （ 1 ） A_n = \begin{bmatrix} F_{n+1} & F_n\\ F_n & F_{n-1} \\ \end{bmatrix}（1）An=[Fn+1FnFnFn−1]（1）
证明方法为数学归纳法，此处不提供证明。
则对于A 2 k A_{2k}A2k, 我们有：
A 2 k = [ F k + 1 F k F k F k − 1 ] 2 = [ F k + 1 2 + F k 2 F k + 1 F k + F k F k − 1 F k + 1 F k + F k F k − 1 F k 2 + F k − 1 2 ] A_{2k} = \begin{bmatrix} F_{k+1} & F_k\\ F_k & F_{k-1} \\ \end{bmatrix}^2 = \begin{bmatrix} F_{k+1}^2 + F_k^2 & F_{k+1} F_{k} +F_{k}F_{k-1} \\ F_{k+1} F_{k} +F_{k}F_{k-1} & F_{k}^2+F_{k-1}^2 \\ \end{bmatrix}A2k=[Fk+1FkFkFk−1]2=[Fk+12+Fk2Fk+1Fk+FkFk−1Fk+1Fk+FkFk−1Fk2+Fk−12]
由于F k − 1 = F k + 1 − F k F_{k-1} = F_{k+1} - F_{k}Fk−1=Fk+1−Fk, 则有：
A 2 k = [ F k + 1 2 + F k 2 F k + 1 F k + F k ( F k + 1 − F k ) F k + 1 F k + F k ( F k + 1 − F k ) F k 2 + F k − 1 2 ] ( 2 ) A_{2k} = \begin{bmatrix} F_{k+1}^2 + F_k^2 & F_{k+1} F_{k} +F_{k}(F_{k+1} - F_k) \\ F_{k+1} F_{k} +F_{k}(F_{k+1} - F_k) & F_{k}^2+F_{k-1}^2 \\ \end{bmatrix} (2)A2k=[Fk+12+Fk2Fk+1Fk+Fk(Fk+1−Fk)Fk+1Fk+Fk(Fk+1−Fk)Fk2+Fk−12](2)
由于n nn也可能是奇数，此事只需要再乘以当获得A 2 k A_{2k}A2k后，计算A 1 A 2 k A_1A_{2k}A1A2k即可。但可根据公式（1），我们可以快速得到：
A 2 k + 1 = [ F 2 k + 2 F 2 k + 1 F 2 k + 1 F 2 k ] = [ F 2 k + 1 + F 2 k F 2 k + 1 F 2 k + 1 F 2 k ] A_{2k+1} =\begin{bmatrix} F_{2k+2} &F_{2k+1} \\ F_{2k+1} &F_{2k} \\ \end{bmatrix} = \begin{bmatrix} F_{2k+1} + F_{2k} &F_{2k+1} \\ F_{2k+1} &F_{2k} \\ \end{bmatrix}A2k+1=[F2k+2F2k+1F2k+1F2k]=[F2k+1+F2kF2k+1F2k+1F2k]
因此，对于分治后合并的每一步，我们首先计算：
F 2 k + 1 = F k + 1 2 + F k 2 F_{2k+1} = F_{k+1}^2 + F_k^2F2k+1=Fk+12+Fk2
F 2 k = F k + 1 F k + F k ( F k + 1 − F k ) = 2 F k + 1 F k − F k 2 F_{2k} = F_{k+1} F_{k} +F_{k}(F_{k+1} - F_k) = 2F_{k+1} F_{k} - F_k^2F2k=Fk+1Fk+Fk(Fk+1−Fk)=2Fk+1Fk−Fk2
k = ⌊ n / 2 ⌋ k = \lfloor n / 2 \rfloork=⌊n/2⌋(下取整）
如果 n nn为奇数，则：
F n + 1 = F 2 k + 1 + F 2 k F_{n+1} = F_{2k+1} + F_{2k}Fn+1=F2k+1+F2k
F n = F 2 k + 1 F_{n} = F_{2k+1}Fn=F2k+1
否则：
F n + 1 = F 2 k + 1 F_{n+1} = F_{2k+1}Fn+1=F2k+1
F n = F 2 k F_{n} = F_{2k}Fn=F2k
示例Python代码：
def fib(self, n):
"""
:type n: int
:rtype: int
"""
self.n = n
_, res = self.util(n)
return res
def util(self, n):
if n == 0:
return 1, 0
#f1 is f_{2k+1}, f2 is f_{2k}
f1, f2 = self.util(n//2)
# Calculate the mutiply first
i = f1 * f1
j = f2 * f2
k = f1 * f2
if n % 2 == 0:
return i + j, 2*k -j
else:
return 2*k + i, i + j