【蓝桥杯】一学就会的小技巧（六）：矩阵快速幂的应用—加速求数列
🐄前言：
- 一学就会的小技巧（一）：前缀和
- 一学就会的小技巧（二）：差分
- 一学就会的小技巧（三）：快速幂
- 一学就会的小技巧（四）：龟速乘
- 一学就会的小技巧（五）：矩阵快速幂
- 数论基础—素数筛、最大公约数、最小公倍数
- 省赛真题—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_晗，计科专业大学牲一枚，请大佬们多多关照~
