从快速幂到矩阵快速幂入门

文章目录[x]
  1. 1:快速幂
  2. 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;
}

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


点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像