算法简介：正绢六通
首先，说到矩阵乘法。字面意思的来讲，就是矩阵与矩阵之间的乘法，他们之间是否满足正常数字之间的乘法规则，也就是交换律与结合律呢？这部分的内容都将在下面被解释。
算法演示：落染五色
矩阵加法：缀锦四分
这个比较简单。首先我们了解一下矩阵的定义，对于一个 $n$ 行 $m$ 列的矩阵，我们有如下的表示方式：
这样的矩阵，就是我们接下来的基础。首先讲到乘法，肯定会有人想到加法。但是实际上……矩阵的加法和乘法几乎一点关系都没有……但是提到了我们也顺便讲一下。
矩阵的运算不同于数字，两个矩阵之间是否可以进行运算，对于矩阵的行和列有着严格的规定。比如说加法，所对应的两个矩阵行和列必须一模一样，因为矩阵加法，就是两个长宽一样的矩阵内的元素一一相加。且满足交换律和结合律。这里给出矩阵的基本定义，以及加法的简单代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Matrix {
public:
int n, m;
vector<vector<ll > > mat;
Matrix(int n, int m) : n(n), m(m), mat(n, vector<ll >(m, 0)) {}
Matrix operator+(const Matrix& B) const {
if(n != B.n || m != B.m) {
return *this;
}
Matrix result(n, m);
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
result.mat[i][j] = (mat[i][j] + B.mat[i][j]) % P;
}
}
return result;
}
};
|
矩阵乘法：衣裁三礼
矩阵之间的乘法，运算的规则比较繁杂。我们说矩阵乘法，需要用第一个乘数矩阵的每一行，去乘以第二个乘数矩阵的每一列。具体的运算过程，可以用下面的表示法表示：
不难发现，我们上面所说的每一行去乘以每一列，其实就说明了这个矩阵乘法的要求，第一个乘数矩阵的列数，要和第二个乘数的行数相等，不然的话做乘法的时候个数对不上。我们用如下的方式表示连个乘法相乘后的结果，也就是当矩阵 $a$ 乘以矩阵 $b$ 的时候，答案矩阵 $c$ 如何表示。
其中我们规定，$a$ 是一个 $r \times c$ 的矩阵，$b$ 是一个 $c\times p$ 的矩阵，那么不难发现答案数组 $c$ 应该是 $r\times p$ 的矩阵。我们可以再举一个例子：
连着几个例子看下来，估计已经可以找到矩阵乘法的规律，并且，不难观察出，这样的乘法形式显而易见不支持交换律，因为他的要求必须精确到某一个乘数的行数或者列数。接下来要提到一个重要的表示法：我们其实是可以用矩阵乘法的表示形式，来描述一个多元一次方程的。比如说下面给出一个二元一次方程组以及他的矩阵表示形式：
矩阵表示，就应该是夏眠这样的，我们称第一个矩阵为系数矩阵，最后一个矩阵为结果矩阵。
这样的表示法极为重要，是接下来构造递推矩阵的答案的非常重要的方式。这里附上矩阵乘法的代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| Matrix operator*(const Matrix& B) const {
if(m != B.n) {
return *this;
}
Matrix result(n, B.m);
for(int i = 0; i < n; ++i) {
for(int j = 0; j < B.m; ++j) {
result.mat[i][j] = 0;
for(int k = 0; k < m; ++k) {
result.mat[i][j] = (result.mat[i][j] + mat[i][k] * B.mat[k][j] % P) % P;
}
}
}
return result;
}
|
矩阵的幂：绫羽二重
说到乘法和幂，不难直接想到我们曾经学过的利器：快速幂。那么矩阵，是否可以用快速幂来计算呢？的确可以，我们回顾一下快速幂的过程。
不难看出来，快速幂的底层逻辑，其实本质上是运用了乘法结合律，而矩阵乘法也可以满足这样的规律。那么也就是说，矩阵也可以有自己的矩阵快速幂。
那么其实有了矩阵乘法的封装，矩阵快速幂的代码就变得极其好写，这一小目的主要内容其实重在矩阵快速幂的运用。下面看一道例题。
求普通斐波那契数列的第 $n$ 项对于 $10^9+7$ 取模的结果（ $1\le n\le 2^{31}-1$ ）
那么这个数据范围其实已经很敏感了。这样 $n$ 的大小甚至支持不了 $O(n)$ 的复杂度。那么我们想想怎么推出斐波那契数列的递推矩阵。我们首先写出斐波那契数列每一位数的关系：
那么我们的目标，是用矩阵递推出后面的内容。可以尝试上面的列方程的形式进行转化。
那么转化的矩阵就是：
转化的过程中一定要注意，他们是关于谁的方程，上下两个式子都特意用了 $f_1,f_2$ 来表示，就是为了凑一个整，可以用方程的形式表达出来，答案那边的 $f_2,f_3$ 只是作为结果出现而已。
并且，推递推矩阵的时候一定要注意：
- 必须得是 $n\times n$ 的矩阵，不然不能快速幂
- 每一个系数都得按照设定未知数的顺序来，如果没有这一项，系数就是 0
这样就可以过掉这道经典的矩阵快速幂题，构造矩阵的方法主要就是这样用方程展示出来的做法，下面放上代码：
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 int128;
typedef pair<int , int > pii;
typedef unsigned long long ull;
namespace FastIO
{
template<typename T> inline T read(T& x) {
x = 0;
int f = 1;
char ch;
while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
x *= f;
return x;
}
template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
read(x);
read(x_...);
return;
}
inline ll read() {
ll x;
read(x);
return x;
}
};
using namespace FastIO;
const int N = 10;
int n, P;
struct Matrix {
int r, c;
ll a[N + 1][N + 1];
Matrix(){}
Matrix(const int &_r, const int &_c) : r(_r), c(_c) {
memset(a, 0, sizeof(a));
}
inline void clear() {
memset(a, 0, sizeof(a));
for (int i = 1; i <= r; i++) a[i][i] = 1;
}
inline Matrix operator * (const Matrix &rhs) const {
Matrix res(r, rhs.c);
for (int i = 1; i <= r; i++)
for (int j = 1; j <= rhs.c; j++) {
for (int k = 1; k <= c; k++) {
res.a[i][j] += a[i][k] * rhs.a[k][j] % P;
res.a[i][j] %= P;
}
}
return res;
}
inline Matrix operator ^ (int p) const {
Matrix res(r, c), x = *this;
res.clear();
for (; p; p >>= 1, x = x * x)
if (p & 1) res = res * x;
return res;
}
};
Matrix ans(2, 2);
inline void Input() {
read(n, P);
}
inline void Work() {
ans.a[1][1] = ans.a[1][2] = ans.a[2][1] = 1;
printf("%lld\n", (ans^(n-1)).a[1][1]);
}
int main() {
int T = 1;
while(T--) {
Input();
Work();
}
return 0;
}
|
算法实战：万理一空
查看相关算法标签喵！
