定义
在数学中，矩阵（Matix） 是一个按照长方形阵列排列的复数或实数集合。
由 \(m \times n\) 个数 \(a_{i,j}\) 排成的 \(m\) 行 \(n\) 列的数表称为 \(m\) 行 \(n\) 列的矩阵，简称 \(m \times n\) 矩阵。(其中 \(m\) 为行数、\(n\) 为列数)
\[\begin{bmatrix}
a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\
a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\
\cdots & \cdots & \cdots & \cdots \\
a_{m,1} & a_{m,2} & \cdots & a_{m,n}
\end{bmatrix}_{m \times n}
\]
几种常见矩阵类型
实矩阵
数表中多有元素均为实数
复矩阵
数表中所有元素均为复数
行矩阵
数表中只有一行元素，没有列元素
列矩阵
数表中只有一列元素，没有行元素
负矩阵
数表中所有元素均为负数
方阵
一种特殊的矩阵，行数 = 列数
\[\begin{bmatrix}
a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\
a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\
\cdots & \cdots & \cdots & \cdots \\
a_{n,1} & a_{n,2} & \cdots & a_{n,n}
\end{bmatrix}_{n \times n}
\]
单位阵
一种特殊的方阵，数表中从左上角到右下角的对角线（称为主对角线）上的元素均为 \(1\) ,除此以外全都为 \(0\) 。
记作 \(I_n\) 或 \(E_n\) ，通常用 \(I\) 或 \(E\) 表示。
根据单位矩阵的特点，任何矩阵与单位矩阵相乘都等于本身。
\[\begin{bmatrix}
1 & 0 & \cdots & 0 \\
0 & 1 & \cdots & 0 \\
\cdots & \cdots & \ddots & \cdots \\
0 & 0 & \cdots & 1
\end{bmatrix}_{n \times n}
\]
同型矩阵
行数和列数分别相同的两个矩阵。
若有
\[A_{m \times n} =
\begin{bmatrix}
a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\
a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\
\cdots & \cdots & \cdots & \cdots \\
a_{m,1} & a_{m,2} & \cdots & a_{m,n}
\end{bmatrix}_{m \times n}
\]
\[B_{m \times n} =
\begin{bmatrix}
b_{1,1} & b_{1,2} & \cdots & b_{1,n} \\
b_{2,1} & b_{2,2} & \cdots & b_{2,n} \\
\cdots & \cdots & \cdots & \cdots \\
b_{m,1} & b_{m,2} & \cdots & b_{m,n}
\end{bmatrix}_{m \times n}
\]
则
\[A_{m \times n} \leftrightarrow B_{m \times n}
\]
那么显然，两个矩阵互为同型矩阵是两个矩阵相同的充分条件。
特殊矩阵
单元素矩阵
当一个矩阵的数表中只有一个元素时，可以不加括号。
\[A=
\begin{bmatrix}
5
\end{bmatrix}
=5
\]
但要注意，一个矩阵 \(5\) 和一个数字 \(5\) 的数学意义是不同的。
零矩阵
数表中所有元素均为零。零矩阵可直接表示为 \((0)\) 或者 \(0\)。
但是值得注意的是，两个零矩阵不一定是同型矩阵，更不一定是相同矩阵，例如
\[0 =
\begin{bmatrix}
0 & 0 & 0 \\
0 & 0 & 0
\end{bmatrix}_{2 \times 3}
\]
与
\[0^{\prime} =
\begin{bmatrix}
0 & 0 \\
0 & 0 \\
0 & 0
\end{bmatrix}_{3 \times 2}
\]
既不是同型矩阵，更不是相同矩阵。
矩阵的对角线
注意，只有方阵才能有对角线，即只有当矩阵的 行数 = 列数 时才能有对角线。
错误示范：
正确示范：
矩阵运算
加减法
将两个矩阵的每一个元素相加减，对应元素形成的结果作为新矩阵的对应元素。
注意：两矩阵能够做加减法运算的充要条件是这两个矩阵是同型矩阵。
\[\begin{aligned}
A_{n \times n} \pm b_{n \times n}
&=
\begin{bmatrix}
a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\
a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\
\cdots & \cdots & \cdots & \cdots \\
a_{n,1} & a_{n,2} & \cdots & a_{n,n}
\end{bmatrix}_{n \times n}
\pm
\begin{bmatrix}
b_{1,1} & b_{1,2} & \cdots & b_{1,n} \\
b_{2,1} & b_{2,2} & \cdots & b_{2,n} \\
\cdots & \cdots & \cdots & \cdots \\
b_{n,1} & b_{n,2} & \cdots & b_{n,n}
\end{bmatrix}_{n \times n} \\
& =
\begin{bmatrix}
a_{1,1} \pm b_{1,1} & a_{1,2} \pm b_{1,2} & \cdots \pm \cdots & a_{1,n} \pm b_{1,n} \\
a_{2,1} \pm b_{2,1} & a_{2,2} \pm b_{2,2} & \cdots \pm \cdots & a_{2,n} \pm b_{2,n} \\
\cdots \pm \cdots & \cdots \pm \cdots & \cdots \pm \cdots & \cdots \pm \cdots \\
a_{n,1} \pm b_{n,1} & a_{n,2} \pm b_{n,2} & \cdots \pm \cdots & a_{n,n} \pm b_{n,n}
\end{bmatrix}_{n \times n}
\end{aligned}
\]
矩阵乘法
数乘矩阵
用一个数乘一个矩阵等于用一个数乘以这个矩阵的全部元素。
\[\begin{aligned}
K \times A_{m \times n}
&=
K \times
\begin{bmatrix}
a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\
a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\
\cdots & \cdots & \cdots & \cdots \\
a_{m,1} & a_{m,2} & \cdots & a_{m,n}
\end{bmatrix}_{m \times n} \\
&=
\begin{bmatrix}
K \times a_{1,1} & K \times a_{1,2} & \cdots & K \times a_{1,n} \\
K \times a_{2,1} & K \times a_{2,2} & \cdots & K \times a_{2,n} \\
\cdots & \cdots & \cdots & \cdots \\
K \times a_{m,1} & K \times a_{m,2} & \cdots & K \times a_{m,n}
\end{bmatrix}_{m \times n} \\
\end{aligned}
\]
矩阵相乘
设 A 为 \(m \times p\) 的矩阵，B 为 \(p \times n\) 的矩阵，那么称 \(m \times n\) 的矩阵 C 为矩阵 A 与 B 的乘积，记作 \(C = A \times B\)，其中矩阵 C 中的第 \(i\) 行第 \(j\) 列元素可以表示为：
\[(A B)_{i j}=\sum_{k=1}^{p} a_{i k} b_{k j}=a_{i 1} b_{1 j}+a_{i 2} b_{2 j}+\cdots+a_{i p} b_{p j}
\]
计算过程：
\[\begin{aligned}
C &=
A_{m \times p} \times b_{p \times n} \\
&=
\begin{bmatrix}
a_{1,1} & a_{1,2} & \cdots & a_{1,p} \\
a_{2,1} & a_{2,2} & \cdots & a_{2,p} \\
\cdots & \cdots & \cdots & \cdots \\
a_{m,1} & a_{m,2} & \cdots & a_{m,p}
\end{bmatrix}_{m \times p}
\times
\begin{bmatrix}
b_{1,1} & b_{1,2} & \cdots & b_{1,n} \\
b_{2,1} & b_{2,2} & \cdots & b_{2,n} \\
\cdots & \cdots & \cdots & \cdots \\
b_{p,1} & b_{p,2} & \cdots & b_{p,n}
\end{bmatrix}_{p \times n} \\
& =
\begin{bmatrix}
a_{1,1} \times b_{1,1} + a_{1,2} \times b_{2,1} + \cdots \times \cdots + a_{1,p} \times b_{p,1}
& a_{1,1} \times b_{1,2} + a_{1,2} \times b_{2,2} + \cdots \times \cdots + a_{1,p} \times b_{p,2}
& a_{1,1} \times \cdots + a_{1,2} \times \cdots + \cdots \times \cdots + a_{1,p} \times \cdots
& a_{1,1} \times b_{1,n} + a_{1,2} \times b_{2,n} + \cdots \times \cdots + a_{1,p} \times b_{p,n} \\
a_{2,1} \times b_{1,1} + a_{2,2} \times b_{2,1} + \cdots \times \cdots + a_{2,p} \times b_{p,1}
& a_{2,1} \times b_{1,2} + a_{2,2} \times b_{2,2} + \cdots \times \cdots + a_{2,p} \times b_{p,2}
& a_{2,1} \times \cdots + a_{2,2} \times \cdots + \cdots \times \cdots + a_{2,p} \times \cdots
& a_{2,1} \times b_{1,n} + a_{2,2} \times b_{2,n} + \cdots \times \cdots + a_{2,p} \times b_{p,n} \\
\cdots \times b_{1,1} + \cdots \times b_{2,1} + \cdots \times \cdots + \cdots \times b_{p,1}
& \cdots \times b_{1,2} + \cdots \times b_{2,2} + \cdots \times \cdots + \cdots \times b_{p,2}
& \cdots \times \cdots + \cdots \times \cdots + \cdots \times \cdots + \cdots \times \cdots
& \cdots \times b_{1,n} + \cdots \times b_{2,n} + \cdots \times \cdots + \cdots \times b_{p,n} \\
a_{m,1} \times b_{1,1} + a_{m,2} \times b_{2,1} + \cdots \times \cdots + a_{m,p} \times b_{p,1}
& a_{m,1} \times b_{1,2} + a_{m,2} \times b_{2,2} + \cdots \times \cdots + a_{m,p} \times b_{p,2}
& a_{m,1} \times \cdots + a_{m,2} \times \cdots + \cdots
\times \cdots + a_{m,p} \times \cdots
& a_{m,1} \times b_{1,n} + a_{m,2} \times b_{2,n} + \cdots \times \cdots + a_{m,p} \times b_{p,n}
\end{bmatrix}_{m \times n}
\end{aligned}
\]
若公式显示不完整可以点击这里查看。
运算律
-
数乘结合律： \(K(AB）=(KA)B=A(KB)\)
-
乘法结合律： \((AB)C=A(BC)\)
-
乘法左分配律： \((A+B)C=AC+BC\)
-
乘法右分配律： \(C(A+B)=CA+CB\)
注意：
若 \(A \times B\) 有意义， \(B \times A\) 不一定有意义。
若 \(A \times B=B \times A\) ，则说明 \(A\) 和 \(B\) 是可交换的。
矩阵加速
P1962 斐波那契数列
一道非常基础的矩乘矩阵加速模板题呢~
注意到数据范围是 \(1 \leq n \leq 2^{63}\) ，肯定不能直接进行常规递推求解。
设
-
\(Fib(n)\) 表示矩阵 \(\begin{bmatrix}F_n & F_{n-1}\end{bmatrix}\) ；
-
\(base\) 使得 \(Fib(n-1) \times base = Fib(n)\) ，即 \(\begin{bmatrix}F_{n-1} & F_{n-2}\end{bmatrix} \times base = \begin{bmatrix}F_n & F_{n-1}\end{bmatrix}\) 。
斐波那契数列的递推式为 \(F_n = F_{n-1} + F_{n-2}\) 。
如果要使得矩阵进行乘法时能令 \(F_{n-1}\) 与 \(F_{n-2}\) 相加，得出 \(F_n\)，那么 \(base\) 矩阵的第一列一定为 \(\begin{bmatrix}1 \\ 1\end{bmatrix}\) 。
同理，如果要计算 \(F_{n-1}\) ，\(base\) 矩阵的第二列一定为 \(\begin{bmatrix}1 \\ 0 \end{bmatrix}\) 。
综上所述，
\[base =
\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}
\]
原式可化为
\[\begin{bmatrix}
F_{n-1} & F_{n-2}
\end{bmatrix}
\times
\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}
=
\begin{bmatrix}
F_n & F_{n-1}
\end{bmatrix}
\]
代码：
/*
Name: P1962 斐波那契数列
Solution: 矩阵加速
By Frather_
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define Kmod 1000000007
#define int long long
using namespace std;
/*==================================================快读*/
inline int read()
{
int X = 0, F = 1;
char CH = getchar();
while (CH < '0' || CH > '9')
{
if (CH == '-')
F = -1;
CH = getchar();
}
while (CH >= '0' && CH <= '9')
{
X = (X << 3) + (X << 1) + (CH ^ 48);
CH = getchar();
}
return X * F;
}
/*===============================================定义变量*/
int n;
struct Matrix
{
int z[3][3];
void init()
{
memset(z, 0, sizeof z);
}
} base, ans;
/*=============================================自定义函数*/
void prepare()
{
ans.init();
ans.z[1][1] = 1;
ans.z[1][2] = 1;
base.init();
base.z[1][1] = 1;
base.z[1][2] = 1;
base.z[2][1] = 1;
}
Matrix mul(Matrix a, Matrix b)
{
Matrix res;
res.init();
for (int i = 1; i <= 2; ++i)
for (int j = 1; j <= 2; ++j)
for (int k = 1; k <= 2; ++k)
res.z[i][j] = (res.z[i][j] + a.z[i][k] * b.z[k][j]) % Kmod;
return res;
}
void Qpow(int b)
{
while (b)
{
if (b & 1)
ans = mul(ans, base);
base = mul(base, base);
b >>= 1;
}
}
/*=================================================主函数*/
signed main()
{
prepare();
n = read();
// if (n <= 2)
// {
// printf("1\n");
// return 0;
// }
Qpow(n - 1);
printf("%lld\n", ans.z[1][2] % Kmod);
return 0;
}
感谢巨佬 @KnightL 为代码优化做出的贡献！！
P1939 【模板】矩阵加速（数列）
上一题的推广版，思路相同。
代码：
/*
Name: P5550 Chino的数列
Solution:
By Frather_
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
// #define int long long
using namespace std;
/*==================================================快读*/
inline int read()
{
int X = 0, F = 1;
char CH = getchar();
while (CH < '0' || CH > '9')
{
if (CH == '-')
F = -1;
CH = getchar();
}
while (CH >= '0' && CH <= '9')
{
X = (X << 3) + (X << 1) + (CH ^ 48);
CH = getchar();
}
return X * F;
}
/*===============================================定义变量*/
int n, s, m, k;
struct Matrix
{
int z[100][100];
Matrix()
{
memset(z, 0, sizeof z);
}
} base, ans;
/*=============================================自定义函数*/
inline Matrix mul(Matrix a, Matrix b)
{
Matrix res;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
for (int k = 1; k <= n; k++)
res.z[i][j] += a.z[i][k] * b.z[k][j];
return res;
}
inline Matrix Qpow(Matrix a, int p)
{
Matrix res;
for (int i = 1; i <= n; i++)
res.z[i][i] = 1;
while (p)
{
if (p & 1)
res = mul(res, a);
a = mul(a, a);
p >>= 1;
}
return res;
}
/*=================================================主函数*/
signed main()
{
n = read();
s = read();
m = read();
k = read();
for (int i = 1; i <= n; i++)
{
ans.z[1][i] = read();
base.z[i % n + 1][i] = 1;
}
swap(base.z[s], base.z[m]);
ans = mul(ans, Qpow(base, k));
for (int i = 1; i <= n; i++)
printf("%d ", ans.z[1][i]);
puts("");
return 0;
}