- 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;
}
矩阵快速幂,简而言之就是利用矩阵加速数列递推,其中最难的也就是怎么推矩阵了,大家可以试一下下面几个例子哦: