矩阵加速学习笔记

Posted on In Word count in article: 4.6k Reading time ≈ 15 mins.
矩阵加速学习笔记

前置知识：矩阵乘法，快速幂

引入

当我们在做题时，常常发现对于某个问题而言可以轻而易举地推出求解的递推式，但如何快速求解就像时挡在我们面前的一座大山，现在我门就来系统的说说如何通过矩阵来加速此类运算。

例子：斐波那契数列

递推式:

fi={1,i≤2fi−1+fi−2,otherwisef_{i} = \begin{cases} 1, & i \leq 2 \\ f_{i - 1} + f_{i - 2}, & otherwise \end{cases}

当需要求解的范围在 10710^{7} 内时我们可以使用 O(n)O(n) 的方法来进行求解，但是如果 n≥107n \geq 10^{7} 时就显得心有余而力不足了，这时候矩阵快速幂就可以解决此类问题。

我们定义一个 1×21 \times 2 的矩阵

mi=[fifi−1]m_{i} = \begin{bmatrix} f_{i} & f_{i - 1} \end{bmatrix}

则：

mi−1=[fi−1fi−2]m_{i - 1} = \begin{bmatrix} f_{i - 1} & f_{i - 2} \end{bmatrix}

不难发现，

mi=mi−1×[1110]m_{i} = m_{i - 1} \times \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}

那么：

mi=m2×[1110]i−2m_{i} = m_{2} \times \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{i - 2}

Talk is cheap. Show me the code.

洛谷 P1962 斐波那契数列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <cstdint>
#include <cstring>
#include <iostream>

using namespace std;

typedef int_fast64_t int64;

constexpr int64 MOD = 1e9 + 7;

int64 n;

class Matrix {
 public:
  int64 row, col;
  int64 num[2][2];
  Matrix(const int64 row, const int64 col) {
    this->row = row;
    this->col = col;
    memset(num, 0, sizeof(num));
  }
};

inline Matrix operator*(const Matrix &lMat, const Matrix &rMat) {
  Matrix res(lMat.row, rMat.col);
  for (int64 i = 0; i < res.row; ++i) {
    for (int64 k = 0; k < lMat.col; ++k) {
      for (int64 j = 0; j < res.col; ++j) {
        res.num[i][j] =
            (res.num[i][j] + (lMat.num[i][k] * rMat.num[k][j]) % MOD) % MOD;
      }
    }
  }
  return res;
}

Matrix base(2, 2), ans(1, 2);

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

int main() {
  ios::sync_with_stdio(false);

  cin >> n;

  if (n <= 2) {
    cout << 1 << endl;
    return 0;
  }

  base.num[0][0] = 1;
  base.num[0][1] = 1;
  base.num[1][0] = 1;

  ans.num[0][0] = 1;
  ans.num[0][1] = 1;

  qpow(n - 2);
  cout << ans.num[0][0] % MOD << endl;

  return 0;
}

如何构造常系数矩阵

在我们推导出递推式后，如何构造一个矩阵来进行矩阵快速幂就成为难点，以下总结了一些常用的方法来构造这个常数矩阵。

无常数项

例子：

fi=fi−1+fi−3f_{i} = f_{i - 1} + f_{i - 3}

由于 fif_{i} 与 fi−1f_{i - 1} 和 fi−3f_{i - 3} 有关，并没有其中的 fi−2f_{i - 2}，如果我们将矩阵设置为：

mi=[fifi−3]m_{i} = \begin{bmatrix} f_{i} & f_{i - 3} \end{bmatrix}

那么就无法通过左乘另一个矩阵来获取 mi+1m_{i + 1}

我们换一种角度思考，当我们需要获取 fif_{i} 时，需要知道 fi−1f_{i - 1} 与 fi−3f_{i - 3}，那么我们就必须要在 mi−1m_{i - 1} 这个矩阵中包含 fi−1f_{i - 1} 与 fi−3f_{i - 3}，则一种新的设计为：

mi=[fifi−2]m_{i} = \begin{bmatrix} f_{i} & f_{i - 2} \end{bmatrix}

那么 fi−2f_{i - 2} 需要知道 fi−5f_{i - 5}，这又令我们难受了，于是我们再次重新设计：

mi=[fifi−1fi−2]m_{i} = \begin{bmatrix} f_{i} & f_{i - 1} & f_{i - 2} \end{bmatrix}

那么这一次惊讶滴发现

mi−1=[fi−1fi−2fi−3]m_{i - 1} = \begin{bmatrix} f_{i - 1} & f_{i - 2} & f_{i - 3} \end{bmatrix}

似乎可以构造常系数矩阵了？

设常系数矩阵为：

K=[k0,0k0,1k0,2k1,0k1,1k1,2k2,0k2,1k2,2]K = \begin{bmatrix} k_{0, 0} & k_{0, 1} & k_{0, 2} \\ k_{1, 0} & k_{1, 1} & k_{1, 2} \\ k_{2, 0} & k_{2, 1} & k_{2, 2} \end{bmatrix}

那么就可以使用如下方法计算 mim_{i} (由于无法使用双下标，所以这里的 M(i,j)M(i, j) 表示的是 MM 矩阵的元素)

mi=[fi−1+fi−3=∑j=02mi−1(0,j)∗K(j,0)fi−2=∑j=02mi−1(1,j)∗K(j,1)fi−3=∑j=02mi−1(2,j)∗K(j,2)]m_{i} = \begin{bmatrix} f_{i - 1} + f_{i - 3} = \sum_{j = 0}^{2}{m_{i - 1}(0, j) * K(j, 0)} & f_{i - 2} = \sum_{j = 0}^{2}{m_{i - 1}(1, j) * K(j, 1)} & f_{i - 3} = \sum_{j = 0}^{2}{m_{i - 1}(2, j) * K(j, 2)} \end{bmatrix}

可以得出

K=[110001100]K = \begin{bmatrix} 1 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix}

常数项与 n 无关

fi=fi−1+fi−2+1f_{i} = f_{i - 1} + f_{i - 2} + 1

易得:

mi−1=[fi−1fi−2fi−31]m_{i - 1} = \begin{bmatrix} f_{i - 1} & f_{i - 2} & f_{i - 3} & 1 \end{bmatrix}

K=[1100101000001001]K = \begin{bmatrix} 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 \\ \end{bmatrix}

常数项与 n1n^{1} 有关

fi=fi−1+fi−2+i−2f_{i} = f_{i - 1} + f_{i - 2} + i - 2

由于矩阵 mi−1m_{i - 1} 需要包含 fi−1f_{i - 1}、fi−2f_{i - 2} 和 i−2i - 2，可知 mim_{i} 需要包含 fif_{i}、fi−1f_{i - 1} 与 i−1i - 1：

mi=[fifi−1i−1]mi−1=[fi−1fi−2i−2]m_{i} = \begin{bmatrix} f_{i} & f_{i - 1} & i - 1 \end{bmatrix} \\ m_{i - 1} = \begin{bmatrix} f_{i - 1} & f_{i - 2} & i - 2 \end{bmatrix}

转移的时候需要将 i−2i - 2 变换为 i−1i - 1，只需要在矩阵中在添加一个元素 11 即可，最终的矩阵如下：

mi=[fifi−1i−11]m_{i} = \begin{bmatrix} f_{i} & f_{i - 1} & i - 1 & 1 \end{bmatrix}

常系数矩阵如下：

K=[1100100010100011]K = \begin{bmatrix} 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 \end{bmatrix}