矩阵乘法

 Tags: 数学  矩阵  Categories: 学习 

设 矩阵与 矩阵相乘得 矩阵，则可记为：

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

矩阵的行数等于 矩阵的行数，而 矩阵的列数等于 矩阵的列数。

简记：左行右列

公式看不懂？举个例子：

设 ， 与 相乘得 。

则 ，于是：

同理类推，，于是：

最后我们就能推出来：

是不是非常神奇 qwq。

参考代码

struct Mat {
  int arr[SIZE][SIZE];
  Mat() { memset(arr, 0, sizeof arr); }
  Mat operator*(const Mat& T) const {
    Mat res; int tmp;
    for (int i = 0; i < SIZE; ++i)
      for (int k = 0; k < SIZE; ++k) {
        tmp = arr[i][k];
          for (int j = 0; j < SIZE; ++j)
            res.arr[i][j] += T.arr[k][j] * tmp, res.arr[i][j] %= MOD;
      }
      return res;
    }
};

/* main() */
Mat C = A * B;

应用

矩阵加速递归（斐波那契数列）

在 斐波那契数列 (Fibonacci Sequence) 中，设 为第 项的值，则 。

那么常规方法就是写 循环一直递归下去，但很显然数量级一大就不行了。

我们定义 矩阵为 ， 矩阵为 ，为其赋初值为 。

可以推得，

于是， 这个元素就等于 的值。

为啥是 次方而不是 次方呢，因为 和 的值本身就是已知的，不需要被计算出来。

Last updated: 2025-01-29