矩阵

定义¶

对于矩阵，主对角线是指的元素。

一般用来表示单位矩阵，就是主对角线上为 1，其余位置为 0。

性质¶

矩阵的逆¶

的逆矩阵是使得的矩阵。

逆矩阵可以用高斯消元的方式来求。

运算¶

矩阵的加减法是逐个元素进行的。

矩阵乘法¶

矩阵相乘只有在第一个矩阵的列数和第二个矩阵的行数相同时才有意义。

设为的矩阵，为的矩阵，设矩阵为矩阵与的乘积，

其中矩阵中的第行第列元素可以表示为：

如果没看懂上面的式子，没关系。通俗的讲，在矩阵乘法中，结果矩阵的第行第列的数，就是由矩阵第行个数与矩阵第列个数分别相乘再相加得到的。

矩阵乘法满足结合律，不满足一般的交换律。

利用结合律，矩阵乘法可以利用快速幂的思想来优化。

在比赛中，由于线性递推式可以表示成矩阵乘法的形式，也通常用矩阵快速幂来求线性递推数列的某一项。

优化¶

可以重新排列循环以提高空间局部性，这样的优化不会改变矩阵乘法的时间复杂度，但是会在得到常数级别的提升。

// 以下文的参考代码为例
inline mat operator*(const mat& T) const {
  mat res;
  for (int i = 0; i < sz; ++i)
    for (int j = 0; j < sz; ++j)
      for (int k = 0; k < sz; ++k) {
        res.a[i][j] += mul(a[i][k], T.a[k][j]);
        res.a[i][j] %= MOD;
      }
  return res;
}
// 不如
inline mat operator*(const mat& T) const {
  mat res;
  int r;
  for (int i = 0; i < sz; ++i)
    for (int k = 0; k < sz; ++k) {
      r = a[i][k];
      for (int j = 0; j < sz; ++j) res.a[i][j] += T.a[k][j] * r;
      res.a[i][j] %= MOD;
    }
  return res;
}

参考代码¶

一般来说，可以用一个二维数组来模拟矩阵。

struct mat {
  LL a[sz][sz];
  inline mat() { memset(a, 0, sizeof a); }
  inline mat operator+(const mat& T) const {
    mat res;
    for (int i = 0; i < sz; ++i)
      for (int j = 0; j < sz; ++j)
        res.a[i][j] = (a[i][j] - T.a[i][j] + MOD) % MOD;
    return res;
  }
  inline mat operator-(const mat& T) const {
    mat res;
    for (int i = 0; i < sz; ++i)
      for (int j = 0; j < sz; ++j) res.a[i][j] = (a[i][j] + T.a[i][j]) % MOD;
    return res;
  }
  inline mat operator*(const mat& T) const {
    mat res;
    int r;
    for (int i = 0; i < sz; ++i)
      for (int k = 0; k < sz; ++k) {
        r = a[i][k];
        for (int j = 0; j < sz; ++j) res.a[i][j] += T.a[k][j] * r;
        res.a[i][j] %= MOD;
      }
    return res;
  }
  inline mat operator^(LL x) const {
    mat res, bas;
    for (int i = 0; i < sz; ++i) res.a[i][i] = 1;
    for (int i = 0; i < sz; ++i)
      for (int j = 0; j < sz; ++j) bas.a[i][j] = a[i][j];
    while (x) {
      if (x & 1) res = res * bas;
      bas = bas * bas;
      x >>= 1;
    }
    return res;
  }
};

应用¶

矩阵加速递推¶

斐波那契数列（Fibonacci Sequence）大家应该都非常的熟悉了。在斐波那契数列当中，，。

如果有一道题目让你求斐波那契数列第项的值，最简单的方法莫过于直接递推了。但是如果的范围达到了级别，递推就不行了，稳 TLE。考虑矩阵加速递推。

设表示一个的矩阵。我们希望根据推出。

试推导一个矩阵，使，即。

怎么推呢？因为，所以矩阵第一列应该是，这样在进行矩阵乘法运算的时候才能令与相加，从而得出。同理，为了得出，矩阵的第二列应该为。

综上所述：原式化为

转化为代码，应该怎么求呢？

定义初始矩阵。那么，就等于这个矩阵的第一行第一列元素，也就是的第一行第一列元素。

注意，矩阵乘法不满足交换律，所以一定不能写成的第一行第一列元素。另外，对于的情况，直接输出即可，不需要执行矩阵快速幂。

为什么要乘上矩阵的次方而不是次方呢？因为是不需要进行矩阵乘法就能求的。也就是说，如果只进行一次乘法，就已经求出了。如果还不是很理解为什么幂是，建议手算一下。

下面是求斐波那契数列第项对取模的示例代码（核心部分）。

const int mod = 1000000007;

struct Matrix {
  int a[3][3];
  Matrix() { memset(a, 0, sizeof a); }
  Matrix operator*(const Matrix &b) const {
    Matrix res;
    for (int i = 1; i <= 2; ++i)
      for (int j = 1; j <= 2; ++j)
        for (int k = 1; k <= 2; ++k)
          res.a[i][j] = (res.a[i][j] + a[i][k] * b.a[k][j]) % mod;
    return res;
  }
} ans, base;

void init() {
  base.a[1][1] = base.a[1][2] = base.a[2][1] = 1;
  ans.a[1][1] = ans.a[1][2] = 1;
}

void qpow(int b) {
  while (b) {
    if (b & 1) ans = ans * base;
    base = base * base;
    b >>= 1;
  }
}

int main() {
  int n = read();
  if (n <= 2) return puts("1"), 0;
  init();
  qpow(n - 2);
  println(ans.a[1][1] % mod);
}

习题¶

洛谷 P1962 斐波那契数列，即上面的例题，同题 POJ3070
洛谷 P1349 广义斐波那契数列，矩阵需要变化一下
洛谷 P1939【模板】矩阵加速（数列），矩阵变成了的矩阵，推导过程与上面差不多。

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

矩阵

定义¶

性质¶

矩阵的逆¶

运算¶

矩阵乘法¶

优化¶

参考代码¶

应用¶

矩阵加速递推¶

习题¶

评论