幂运算

## 快速幂

1. **求 $x^n$ 最简单的方法是通过循环将 $n$ 个 $x$ 乘起来**，**依次求 $x_1, x_2,..., x_n$**，**时间复杂度为 $O(n)$**，而**快速幂算法可将时间复杂度降低至 $O(log_n)$**。
2. **快速幂算法实际上是二分思想的一种应用**，具体推导如下：
   1. $x^n = x^{n / 2} \times x^{n / 2}$，令 $n / 2$ 为整数，则需要分为奇偶两种情况（设向下取整除法符号为 `//`）：
      1. **当 $n$ 为偶数**：$x^n = (x^2)^{n // 2}$。
      2. **当 $n$ 为奇数**：$x^n = x(x^2)^{n // 2}$，即**会多出一项 $x$**。
3. **幂结果的获取方法**如下：
   1. **根据二分推导**，**可通过循环$x = x^2$操作**，**每次把幂从$n$降至$n // 2$**，**直至将幂降为0**。
   2. **设$res = 1$**，**则初始状态$x^n = x^n \times res$**，**在循环二分时**，**每当$n$为奇数时**，**将多出的一项$x$乘入$res$**，**则最终可化至$x^n = x^0 \times res = res$**，**返回$res$即可**。

![Picture2.png](https://notebook.ricear.com/media/202202/2022-02-08_1930410.5592932205133178.png)
4. 计算过程中**部分操作可转化为位运算**：
   1. **向下整除$n // 2$等价于右移一位**，即$n >> 1$。
   2. **取余数$n % 2$等价于判断二进制最右一位值**，即$n \& 1$。

5. 具体代码如下：

```java
   public int quickPow(int x, int n) {
       int res = 1;
   
       if (x == 0) {return 0;}  // if x equal 0, then return 0, just to avoid divide zero error
       if (n < 0) {  // if x smaller than 0, then reverse x
           x = 1 / x;
           n = -n;
       }
   
       while (n > 0) {  // get pow(x, n) with quick pow
           if ((n & 1) == 1) {res *= x;}
           x *= x;
           n >>= 1;
       }
       return res;
   }
   ```

> [剑指 Offer 16. 数值的整数次方](https://leetcode.cn/problems/shu-zhi-de-zheng-shu-ci-fang-lcof) 可采用类似的方法来求解。

## 矩阵快速幂

1. 假设 $f(n) = f(n-1) + f(n - 2)$，令
   $$
   A_n = \begin{pmatrix}f_{n+1}\\f_{n}\end{pmatrix} = \begin{pmatrix}f_n+\;f_{n-1}\\f_n\;\end{pmatrix} = \begin{pmatrix}1&1\\1&0\end{pmatrix}\begin{pmatrix}f_n\\f_{n-1}\end{pmatrix} = \begin{pmatrix}1&1\\1&0\end{pmatrix}A_{n-1}
   $$
   令 $B = \begin{pmatrix}1&1\\1&0\end{pmatrix}$，则
   $$
   A_n = B A_{n-1} = B^2 A_{n-2} = \cdots = B^n A_0
   $$

2. 由于矩阵乘法满足结合律，因此矩阵 $B$ 的幂次运算也可以通过「**快速幂**」进行加速，通过快速计算 $B^n$，再将其与矩阵 $A_0$ 相乘，即可得到 $f(n)$，将原来 $O(n)$ 的递推加速至 $O(logn)$，这一过程被称为「**矩阵快速幂**」，矩阵快速幂的代码如下所示：

> 矩阵的快速幂和整数的快速幂类似，只不过乘法计算时 **矩阵乘法**。

> 由于 $A_{n - 1}$ 中已经包含了 $f(n)$，因此计算到 $B_{n - 1}$ 即可。

```java
   /**
    * 矩阵快速幂
    * @param x 矩阵
    * @param n 幂数
    * @return  x 的 n 次幂
    */
   public int[][] quickMatrixPow(int[][] x, int n) {
       int[][] res = new int[x.length][x.length];
       for (int i = 0; i < x.length; i++) {
           res[i][i] = 1;
       }
       if (n == 0) {return res;}
       if (n == 1) {return x;}
       while (n > 0) {
           if ((n & 1) == 1) {res = matrixMultiply(res, x);}
           n >>= 1;
           x = matrixMultiply(x, x);
       }
       return res;
   }
   
   /**
    * 矩阵乘法
    * @param a 第一个矩阵
    * @param b 第二个矩阵
    * @return  两个矩阵相乘的结果
    */
   public int[][] matrixMultiply(int[][] a, int[][] b) {
       int[][] res = new int[a.length][b[0].length];
       for (int i = 0; i < a.length; i++) {    //  矩阵 a 的第 i 行
           for (int j = 0; j < b[0].length; j++) { //  矩阵 b 的第 j 列
               int sum = 0;    //  矩阵第 i 行和矩阵 b 的第 j 列相乘的结果
               for (int k = 0; k < a[i].length; k++) {
                   sum += a[i][k] * b[k][j];
               }
               res[i][j] = sum;
           }
       }
       return res;
   }
   ```

## 参考文献

1. [剑指 Offer 16. 数值的整数次方](https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof)。
2. [面试题 16. 数值的整数次方（快速幂，清晰图解）](https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/solution/mian-shi-ti-16-shu-zhi-de-zheng-shu-ci-fang-kuai-s)。
3. [一题 N 解的爬楼梯问题，递归、动态规划、矩阵快速幂~](https://blog.ficowshen.com/page/post/67)。
4. [《面试必考的「矩阵快速幂」考点汇总》 ](https://mp.weixin.qq.com/s?__biz=Mzg5MjcwMDc3MQ==&mid=2247489664&idx=1&sn=c96e9c5a1f28b236acdb0d2ad4ddf68e&source=41#wechat_redirect)。