递推递归类问题 矩阵快速幂解法 学习笔记

· · 算法·理论

前置知识

递推类问题解题思路

以斐波那契数列问题为例：

对于递归表达式 f(x)=f(x-1)+f(x-2)

构造递归起始列矩阵：

\begin{bmatrix} f(n-1) \\ f(n-2) \end{bmatrix}

构造递归终止列矩阵：$E= \begin{bmatrix} f(n) \ f(n-1) \end{bmatrix}

设 $M_{2,2}$ 为左转移矩阵，则有 $E = M \cdot S

推导可得 $M= \begin{bmatrix} 1 & 1 \ 1 & 0 \end{bmatrix}

则有： $$ \begin{bmatrix} f(n) \\ f(n-1) \end{bmatrix}= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \cdot \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}^2 \cdot \begin{bmatrix} f(n-2) \\ f(n-3) \end{bmatrix} $$ $$ \begin{bmatrix} f(n) \\ f(n-1) \end{bmatrix}= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^3 \cdot \begin{bmatrix} f(n-3) \\ f(n-4) \end{bmatrix} $$ $$\vdots$$ $$ \begin{bmatrix} f(n) \\ f(n-1) \end{bmatrix}= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n-2} \cdot \begin{bmatrix} f(2) \\ f(1) \end{bmatrix} $$ # 快速幂优化 如果 n 很大的时候，例如：n $\leq 10^{18}$ 时，$O(n)$ 的复杂度肯定无法在 1.0s 内跑出来。所以此时，我们需要用到快速幂算法进行优化。 ## 快速幂算法思想及原理 我们已知 $a$ 自乘一次得到的结果是 $a^2$, 自乘两次得到的结果是 $a^4$, 自乘三次得到的结果是 $a^3 \cdots$, 自乘 $n$ 次得到的结果是 $a^{2^n}$。 那么我们以运算 $3^{10}$ 为例： $\because10=(1010)_{2}=2^3+2^1=8+2 \therefore3^{10}=3^8\times3^2=3^{2^3}\times3^{2^1}

所以此时我们可以现将底数 3 自乘一次得到 3^{2^1} 即 3^2，将其与当前总结果 1 相乘，得到 3^2。在将底数底数 3 自乘三次得到 3^{2^3} 即 3^8，将与当前的总结果 3^2 相乘，得到 3^2\times3^8=3^{10}, 即我们想要的结果。

根据上面的操作，我们可以发现： 当我们在运算 a^b 时，我们只需将 b 进行二进制分解。 若 b\ne0， 则每次进行如下操作：

  1. 若 b 用二进制表示的最低位为 1, 则说明此时 a 已经自乘足够的次数，我们需要将其更新至总答案中，并将 b 的这一最低二进制位由 1 变为 0。随后，按照 b 用二进制表示的最低位为 0 的情况继续处理。
  2. 若 b 用二进制表示的最低位为 0, 则说明此时 a 还没有自乘足够的次数，a 自乘，不用将其更新至总答案中。
  3. 已经处理完 b 用二进制表示的最低位，需要继续处理下一位。此时，我们只需将 b 右移一位，即除以二。在下一次处理时，待处理的 b 用二进制表示的次低位就成为了 b 用二进制表示的最低位。
  4. 重复这个过程，直至 b=0。

下附快速幂函数模板代码：

int qm (int n) {//快速幂
    int res=1;//result 一定要初始化为1，不然可能用0乘了很多次，最终结果还是0，乘了个寂寞
   int trans=base;//transfer base是底数a
    while (n) {// n次方
        if (n&1) res=res*trans;//该二进制位上是1，将临时存储变量 transfer 的值，转移到结果 result 上
        trans=trans*trans;//该二进制位上是0，临时存储变量 transfer 自乘
        n>>=1;//二进制右移一位（除以二）
   }
}

参考文献

快速幂和取余运算

更新日记

4.13 打出了基本框架

4.16 修复了 \LaTeX 渲染问题，并对快速幂优化部分进行了详细介绍