#### 快速幂

$$x^{11} = x ^ {2^3} × x ^ {2^1} × x^{2^0} = x^8 × x^2 × x^1$$

• 11 = 1011
• 1：res = $x^{2^0}$
• 1: res = $x^{2^0} × x^{2^1}$
• 0: 跳过，不运算
• 1：res = $x^{2^0} × x^{2^1} × x^{2^3}$

• n and 1 返回1， 则n是奇数，即n的二进制低位是1
• n and 1 返回0， 则n是偶数，即n的二进制低位是0

• n = n >> 1 = 1011 >> 1 = 101
• n = n >> 1 = 101 >> 1 = 10
• n = n >> 1 = 10 >> 1 = 1
• n = n >> 1 = 1 >> 1 = 0

#### 矩阵乘法

$$C = AB = \begin{bmatrix} 1 & 2 \\ 3 & 4 \\ \end{bmatrix} × \begin{bmatrix} 5 & 6 \\ 7 & 8 \\ \end{bmatrix} = \begin{bmatrix} 1×5+2×7 & 1×6+2×8 \\ 3×5+4×7 & 3×6+4×8 \\ \end{bmatrix} = \begin{bmatrix} 19 & 22 \\ 43 & 50 \\ \end{bmatrix}$$

$$A^{11} = A^8 × A^2 × A^1 = \begin{bmatrix} 1 & 2 \\ 3 & 4 \\ \end{bmatrix} ^ 8 × \begin{bmatrix} 1 & 2 \\ 3 & 4 \\ \end{bmatrix} ^ 2 × \begin{bmatrix} 1 & 2 \\ 3 & 4 \\ \end{bmatrix} ^ 1$$

#### 扩展：斐波那契数列矩阵算法

• $F(0) = 0$
• $F(1) = 1$
• $F(n) = F(n-1) + F(n-2) (n>=2)$

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……（OEIS中的数列A000045）

$$\begin{bmatrix} F(n)=F(n-1)+F(n-2) \\ F(n-1) \\ \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix} × \begin{bmatrix} F(n-1) \\ F(n-2) \\ \end{bmatrix}$$

$$\begin{bmatrix} F(n) \\ F(n-1) \\ \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix} × \begin{bmatrix} F(n-1) \\ F(n-2) \\ \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix}^2 × \begin{bmatrix} F(n-2) \\ F(n-3) \\ \end{bmatrix} = … = \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix}^{n-1} × \begin{bmatrix} F(1) \\ F(0) \\ \end{bmatrix}$$