基础知识

矩阵定义

晚点写。

矩阵加法/矩阵减法

晚点写

矩阵乘法

前置条件

矩阵乘法有意义，当且仅当第一个矩阵的列数和第二个矩阵的行数相同时。

则此时两个矩阵相乘的行数为第一个矩阵的行数，列数为第二个矩阵的列数。

可以记为将两个矩阵相同的一个边长去掉，然后第一个矩阵剩余的边长作为最终结果的行数，第二个矩阵剩余的边长作为最终结果的列数。

故设 P 为 a × b 的矩阵，Q 为 b × c 的矩阵。

设 R 为矩阵 P 与 Q 的乘积，则大小为 a × c。

运算法则

矩阵 R 中的第 i 行第 j 列元素可以表示为

一种可能的记忆方法

对于 A 矩阵的第 i 行，将其顺时针旋转 ，并将其与 B 矩阵的第 j 列每个对应的数相乘，其和即为 Ci, j。

举个例子：

A 为 4 × 6 的矩阵，B 为 6 × 2 的矩阵，则 C 为 4 × 2 的矩阵。

假设要求 C3, 2，则取出 A 矩阵第 3 行，将其顺时针旋转 ，可得 A′。同时去除 B 矩阵第二列，将 A′ 与 B 第二列位于同一行的数乘起来，最后将所有乘积求和即得 C3, 2。

性质

矩阵乘法满足结合律，即 (A × B) × C = A × (B × C)。

矩阵乘法不满足交换律，即 A × B ≠ B × A。

矩阵快速幂

由于矩阵满足结合律，所以可以对乘法的次数进行二进制拆分，那么就可以和普通的快速幂一样了。

需要注意的是，没有快速幂的目标矩阵 A0 应该是单位矩阵 I。

矩阵模板

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
template<typename T> // T 表示矩阵存的值的类型
struct Matrix {
	size_t n, m; // n 为行数，m 为列数
	std::vector<std::vector<T>> a;
	Matrix(size_t _n = 0, size_t _m = 0) : n(_n), m(_m) {
		a.resize(_n);
		for (size_t i = 0; i < _n; ++i)
			a[i].resize(_m);
	}
  Matrix(const std::vector<std::vector<T>> &_a) : n(_a.size()), m(_a[0].size()), a(_a) {}
  void build() { for (size_t i = 0; i < n; ++i) a[i][i] = 1; }
	Matrix<T> operator*(const Matrix<T> &A) {
		if (m != A.n) throw "Error";
		Matrix<T> res(n, A.m);
		for (size_t i = 0; i < n; ++i) // 枚举最终矩阵的行
			for (size_t j = 0; j < A.m; ++j) // 枚举最终矩阵的列
				for (size_t k = 0; k < m; ++k) // 枚举 A 的列（B 的行）
					res.a[i][j] += a[i][k] * A.a[k][j]; // 实际实现中可能需要取模
		return res;
	}
  void operator*=(const Matrix<T> &A) {
    *this = *this * A;
  }
};

template <typename T>
std::istream &operator>>(std::istream &is, Matrix<T> &A) { // 读入矩阵
	for (size_t i = 0; i < A.n; ++i)
		for (size_t j = 0; j < A.m; ++j)
			is >> A.a[i][j];
	return is;
}

template <typename T>
std::ostream &operator<<(std::ostream &os, const Matrix<T> &A) { // 输出矩阵
	for (size_t i = 0; i < A.n; ++i) {
		for (size_t j = 0; j < A.m; ++j)
			os << A.a[i][j] << ' ';
		os << '\n';
	}
	return os;
}

template <typename T>
Matrix<T> qpow(Matrix<T> &P, size_t b) { // 矩阵快速幂
  Matrix<T> ans(P.a.size(), P.a.size());
  ans.build();
  for (; b; b >>= 1) {
    if (b & 1) ans *= P;
    P *= P;
  }
  return ans;
}

题目分析

矩阵 - 题单 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

矩阵乘法/【模板】矩阵快速幂

直接套用模板即可，无需多说。

矩阵加速（数列）

题意简述

已知一个数列 a，它满足：

求 a 数列的第 n (1 ≤ n ≤ 2 × 109) 项对 109 + 7 取余的值。

算法分析

由于 n 的范围较大，递推显然会 TLE，所以可以使用矩阵加速递推。

由于当前值 ax 与前三项值相关，故设计 所以我们希望得到一个矩阵 P，使得 P × f(x − 1) = f(x)，然后进行转移。 由于最终结果为 3 × 1 的矩阵，而一个乘矩阵为 3 × 1，所以 P 应为大小 3 × 3 的矩阵。

设第一行的数依次为 i, j, k，那么要使得 i × ax − 3 + j × ax − 2 + k × ax − 1 = ax − 2，那么显然 i = k = 0, j = 1。

同理，第二行依次为 0, 0, 1。

设第三行的数以此为 y, z, w，那么 y × ax − 3 + z × ax − 2 + w × ax − 1 = ax = ax − 1 + ax − 3 ⇒ y = 1, z = 0, w = 1 故 所以 那么 中的 p 是多少呢？

考虑举例子。

当 n = 4 时，p = 1 即可符合要求。

故 p = n − 3。

对于前一个矩阵可以用矩阵快速幂在 log n 的时间内求出，再进行依次矩阵乘法即可。

特别的，对应 n ≤ 3 的情况要进行特判，直接输出 1。

时间复杂度为 O(T × L3log n))，其中 L = 3。

斐波那契数列

题意简述

斐波那契数列是满足如下性质的一个数列：

请你求出 Fn mod  (109 + 7) 的值 1 ≤ n < 263。

算法分析

n 的范围较大，难以递推。由于递推式已知，故可以使用矩阵加速递推。

由于 Fn 仅和 Fn − 1, Fn − 2 有关，故设计

故矩阵 P 为 2 × 2 的矩阵，且满足 P × f(x − 1) = f(x)。

使用待定系数法，可得 所以

同理快速幂要乘的次数为 n = 2 次。

由此可以发现一个规律，设特判的数为 1 ∼ i，那么第 n (n > i) 项的快速幂次数为 n − i。

时间复杂度为 O(L3log n)，其中 L = 2。

广义斐波那契数列

题意简述

广义的斐波那契数列是指形如 an = p × an − 1 + q × an − 2 的数列。

给定数列的两系数 p 和 q，以及数列的最前两项 a1 和 ，另给出两个整数 n 和 m，试求数列的第 n 项 an 对 m 取模后的结果。

算法分析

考虑矩阵加速递推。

an 只和 an − 1 和 an − 2 有关，所以设计 。

可知 P 为 2 × 2 的矩阵，且 P × f(x − 1) = f(x)。

令 ，那么有 则可得 所以 。

故 时间复杂度为 O(L3log n)，其中 L = 2。

斐波那契公约数

题意简述

对于 Fibonacci 数列：

请求出 gcd (fn, fm) mod  108。

算法分析

引理：gcd (fi, fj) = fgcd (i, j)。

证明

晚点写。

那么直接用矩阵快速幂求出 fgcd (n, m) 即可。

时间复杂度 O(L3log gcd (n, m))，其中 L = 2。