- 1:快速幂
- 2:矩阵快速幂
csdn博客链接：https://nuoyanli.blog.csdn.net/article/details/105314274
从快速幂到矩阵快速幂入门
快速幂
假设大家已经快忘记了快速幂这个东西
一般对于我们只需要连续乘次就能得到答案了：
例如
- 只需要连续乘次即可，
- 只需要连续乘次即可，
- 如果你觉得还好，那么呢？
回归到问题本身，当很大的时候，是很费时间的，直接乘个往往会超时，所以就有了快速幂这个算法。
我们以为例，把写成二进制：
那么
通过观察我们不难发现，当的二进制第位上为，就乘上，这个值是可以由前面递乘出来的，所以这样一来大大减少了计算次数：
推广到
①若为偶数，
②若为奇数，
可以看到幂是指数级别下降的，因此最终复杂度是而不是朴素算法的。
板子如下：
int qpow(int a, int b) {
int ans = 1;
while (b) {
if (b & 1) {
ans *= a;
}
a *= a;
b >>= 1;
}
return ans;
}
int qpow_mod(int a, int b, int c) {
a = a % c;
int ans = 1;
while (b) {
if (b & 1) {
ans = ans * a % c;
}
a = a * a % c;
b >>= 1;
}
return ans;
}
矩阵快速幂
那么矩阵快速幂又是什么呢？
矩阵快速幂就是把整数变成矩阵用快速幂来算其次方而已，，其中，像这样的就是矩阵快速幂，那么为啥会有矩阵快速幂这个东西呢？
首先提一下矩阵的前置知识：
相信到这学期，大家已经学过了线性代数相关知识，我就不过多解释：
矩阵的一些名词定义：
- 阶矩阵：这就是一个的矩阵，也叫阶矩阵
- 行向量：只有一行的矩阵，也叫行矩阵，这就是一个行向量
- 列向量：只有一列的矩阵，也叫列矩阵，，这就是一个列向量。
矩阵的相关运算：
- 矩阵加法：设有两个的矩阵，那么矩阵与的和记做，规定为：
，也就是对应相加重新构成的一个矩阵。
这里要注意的是，只有当两个矩阵是同型矩阵（也就是行数相等列数也相等）时，这两个矩阵才能进行加法运算。
- 矩阵乘法：设有两个的矩阵，
一般，我们设是一个的矩阵，是一个矩阵，那么规定矩阵与矩阵的乘积是一个的矩阵，其中：
并把此乘积记作:，也叫矩阵左乘矩阵，这里可以发现，矩阵的乘法是不满足交换律的，故乘法顺序对矩阵的影响。
也就是矩阵的对应行的每一个乘矩阵的对应列的每一个，然后相加构成的。
我们介绍完了矩阵的知识，那大家一定会问，矩阵快速幂有啥用呢？
我们不妨先回想忆一下斐波拉契数列，
如果我们要求某一项是要的时间复杂度的，那么我们有没有一种可能降低时间复杂度呢？
答案是显然的，我们可以用上面说到的矩阵加速，我们不妨有这样的设想：
每个矩阵都可以独立的退出其后的所有矩阵，因为矩阵里面包含了所有有用的状态。
所以，我们只需要知道矩阵直接的箭头是什么操作，就可以利用第个矩阵推出之后的所有矩阵。
我们把第一步单独拿出来：
把拆成：
然后稍微补充一下，构造完整的矩阵：
第二个矩阵的形式我们是不是有点似曾相识....没错，这就是矩阵乘法：
所有，上面那个递推过程中的箭头操作就是矩阵乘法操作，想到这里大家是不是释然了？
......
所以：
显然：矩阵快速幂！！！
只需要将上面的整数快速幂代码改成矩阵的即可了，详见代码：
以POJ3070为例：
#include <iostream>
using namespace std;
typedef long long LL;
const int mod = 10000;
const int N = 110;
int n = 2;
struct mat {
int m[N][N];
} Mat;
mat operator*(mat a, mat b) {
mat ret;
LL x;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
x = 0;
for (int k = 0; k < n; k++) {
x = (x + a.m[i][k] * b.m[k][j]) % mod;
}
ret.m[i][j] = x % mod;
}
}
return ret;
}
void init_Mat() {
for (int i = 0; i < N; i++) {
Mat.m[i][i] = 1;
}
}
mat pow_mat(mat a, LL n) {
mat ret = Mat;
while (n) {
if (n & 1) {
ret = ret * a;
}
a = a * a;
n >>= 1;
}
return ret;
}
int main() {
LL p;
init_Mat();
while (cin >> p && p != -1) {
mat a;
a.m[0][0] = 1;
a.m[0][1] = 1;
a.m[1][0] = 1;
a.m[1][1] = 0;
a = pow_mat(a, p);
cout << a.m[0][1] << endl;
}
return 0;
}
矩阵快速幂，简而言之就是利用矩阵加速数列递推，其中最难的也就是怎么推矩阵了，大家可以试一下下面几个例子哦：