[数据结构与算法]【蓝桥杯】一学就会的小技巧（六）：矩阵快速幂的应用—加速求数列

🐄前言：

• 一学就会的小技巧（一）：前缀和
• 一学就会的小技巧（二）：差分
• 一学就会的小技巧（三）：快速幂
• 一学就会的小技巧（四）：龟速乘
• 一学就会的小技巧（五）：矩阵快速幂
• 数论基础—素数筛、最大公约数、最小公倍数
• 省赛真题—K倍区间（前缀和，数学，思维）

🌵🌵本文是小技巧系列的最后一篇文章了，在前面的几篇文章中，带大家从快速幂一直拓展到矩阵快速幂，矩阵快速幂最重要的一个应用就是可以根据数列通项加速求数列第n项。

🍄数列加速：

👩🏻?🏫以斐波那契数列为例，看看如何利用矩阵快速幂求数列的第n项。

👉🏻思路：

• 附上我的手写笔记，字丑见谅哈哈~😛

• 将数列写成矩阵时上下的顺序也可调换，比如官方题解这样，只是需要进行快速幂的矩阵发生了变化，不影响最终结果，推到过程也是一样的~

  

🍦AC代码（Java）：

class Solution {

    public static final long mod = 1000000007;

    public static long[][] matrixMultiply(long[][] matrixA, long[][] matrixB) {
        int n = matrixA.length, p = matrixB.length, m = matrixB[0].length;
        if (p != matrixA[0].length)
            return null;
        long[][] ans = new long[n][m];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                for (int k = 0; k < p; k++)
                    ans[i][j] += (matrixA[i][k] % mod) * (matrixB[k][j] % mod) % mod;
                ans[i][j] = ans[i][j] % mod;
            }
        return ans;
    }

    public static long[][] fastMatrixPow(long[][] matrix, long k) {
        int len = matrix.length;
        long[][] res = new long[len][len];
        for (int i = 0; i < len; i++)
            res[i][i] = 1;
        while (k > 0) {
            if ((k & 1) == 1)
                res = matrixMultiply(res, matrix);
            matrix = matrixMultiply(matrix, matrix);
            k = k >> 1;
        }
        return res;
    }

    public int fib(int n) {
        if (n < 2) {
            return n;
        }
        long[][] q = {{1, 1}, {1, 0}};
        long[][] res = fastMatrixPow(q, n - 1);
        return (int)res[0][0];
    }
}

• 其实就是上篇文章矩阵快速幂的模板，不能说非常相像，只能说一模一样😛

• 执行时间击败100%，要比常规的解法快很多~

🍌🍌🍌
本文介绍了第六个小技巧——数列加速，利用矩阵快速幂求数列，室友看了直呼牛🍺~
🍍🍍🍍
创作不易，如果觉得本文对你有所帮助的话请动动小手，给博主点个免费的赞吧。🙇🏻?♀?
🍉🍉🍉
@作者：Mymel_晗，计科专业大学牲一枚，请大佬们多多关照~