复习心得 - 矩阵
ExFish
·
·
算法·理论
二维数组（？）
定义
一个 m\times n 个数构成一个矩阵 \text{A}，或者 \text{A}_{\text{mn}}。
\text{A}=\begin{bmatrix}
a_{11} & a_{12} & a_{13} & \dots & a_{1n}\\
a_{21} & a_{22} & a_{23} & \dots & a_{2n} \\
a_{31} & a_{32} & a_{33} & \dots & a_{3n} \\
\dots & \dots & \dots & \dots & \dots \\
a_{m1} & a_{m2} & a_{m3} & \dots & a_{mn}
\end{bmatrix}
其中 (a_{ij})（或 (a_{ij})_{m\times n}） 是矩阵 \text{A} 的元素。
矩阵 +
就是直接加了。
注意 n 和 m 都要相等。
\text{A}_{32}=\begin{bmatrix}
1 & 1 & 4 \\
5 & 1 & 4 \\
\end{bmatrix}
\text{B}_{32}=\begin{bmatrix}
1 & 9 & 1 \\
9 & 8 & 1
\end{bmatrix}
这时
\text{A}+\text{B}=\begin{bmatrix}
1+1 & 1+9 & 4+1 \\
5+9 & 1+8 & 4+1 \\
\end{bmatrix}=\begin{bmatrix}
2 & 10 & 5 \\
14 & 9 & 5 \\
\end{bmatrix}
矩阵加法满足交换律和结合律。
矩阵 -
这个不举例了，就是逆运算了。
数乘 · 不是矩乘！
\text{A}_{32}=\begin{bmatrix}
1 & 1 & 4 \\
5 & 1 & 4 \\
\end{bmatrix}
这时
v\cdot\text{A}_{32}=\begin{bmatrix}
v & v & 4v \\
5v & v & 4v \\
\end{bmatrix}
矩阵数乘满足交换律、结合律和分配律。
矩阵转置
对角线翻折，记作 A^T。
\text{A}=\begin{bmatrix}
1 & 1 & 4 \\
5 & 1 & 4 \\
\end{bmatrix}
这时
\text{A}^T=\begin{bmatrix}
1 & 5 \\
1 & 1 \\
4 & 4 \\
\end{bmatrix}
我们发现相当于 A_{ij}\to{A^T}_{ji}。
矩阵转置满足反身性、可乘性。（点乘、矩乘）
矩乘 *
在这个例子中，\text{A}_{np} 和 \text{B}_{pm} 是我们的两个矩阵。
具体的来说，就是：
\text{C}_{ij}=\sum _{k=1}^p\text{A}_{ik}\cdot\text{B}_{kj}
这个建议手玩。
矩阵结果就是：
\text{A}_{np}\ \text{B}_{pm}=\text{C}_{nm}
注意：这样定义的矩乘不满足 \text{AB}=\text{BA}。
但是满足：
初等变换（行）
列变换极其相似，这里省略。
- 对一整行乘上一个 val（val\in \text{R} 且 val\neq 0）
- 一行加上另一行。
- 交换两行。
对矩阵进行这些操作之一就是初等变换。注意到这个东西很像一次方程的消元，高斯消元法就是用这个东西。
特殊矩阵
- 稀疏矩阵：非 0 元素比较少。可以优化乘法。
- 上三角：主对角线以下元素全为 0，如
\begin{bmatrix}
1 & 1 & 1 \\
{\color{red}0} & 1 & 1 \\
{\color{red}0} & {\color{red}0} & 1 \\
\end{bmatrix}
\begin{bmatrix}
1 & {\color{red}0} & {\color{red}0} \\
1 & 1 & {\color{red}0} \\
1 & 1 & 1 \\
\end{bmatrix}
\begin{bmatrix}
1 & 2 & 3 \\
2 & 4 & 6 \\
3 & 6 & 9 \\
\end{bmatrix}
\begin{bmatrix}
1 & {\color{red}0} & {\color{red}0} \\
{\color{red}0} & 2 & {\color{red}0} \\
{\color{red}0} & {\color{red}0} & 9 \\
\end{bmatrix}
\text{I}=\begin{bmatrix}
1 & {\color{red}0} & {\color{red}0} \\
{\color{red}0} & 1 & {\color{red}0} \\
{\color{red}0} & {\color{red}0} & 1 \\
\end{bmatrix}
- 这个东西的性质：\text{AI}=\text{A}，就是怎么乘都不会变。特别的，对这个矩阵进行初等变换后的矩阵称为初等矩阵 \text{E}。
矩阵快速幂
我们有一个递推式：
\begin{bmatrix}
F_{n} & F_{n-1} & \dots & F_{n-k+1}
\end{bmatrix}
我们要由
\begin{bmatrix}
F_{n-k+1} & F_{n-k} & \dots & F_{n-2(k+1)}
\end{bmatrix}
的矩阵推出来。
我们中间就需要一个转移矩阵。
\text{Base}=\begin{bmatrix}
b_{11} & b_{12} & \dots & b_{1k} \\
b_{21} & b_{22} & \dots & b_{2k} \\
\dots & \dots & \dots & \dots \\
b_{k1} & b_{k2} & \dots & b_{kk} \\
\end{bmatrix}
我们发现这满足 \begin{bmatrix}
F_{n-k+1} & F_{n-k} & \dots & F_{n-2(k+1)}
\end{bmatrix}\times \text{Base}= \begin{bmatrix}
F_{n} & F_{n-1} & \dots & F_{n-k+1}
\end{bmatrix}。
然后我们直接快速幂就可以快速根据初始矩阵转移出答案 F_{n}。
斐波那契数列
由于下方只有构造矩阵有意义，所以只给出矩阵。
我们有一个目标的矩阵：
\begin{bmatrix}
F_n & F_{n-1}
\end{bmatrix}
我们一开始有一个初始的矩阵：
\begin{bmatrix}
F_2 & F_{1}
\end{bmatrix}=
\begin{bmatrix}
1 & 1
\end{bmatrix}
我们怎么转移呢？
\text{Base}=\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}
即 F_{n}=1\times F_{n-1}+1\times F_{n-2}，F_{n-1}=1\times F_{n-1}+0\times F_{n-2}。
斐波那契数列的和
即 s_n=\sum_{i=1}^nf_{i}。
偷懒者：我不推矩阵。
我们发现 s_n=2\times f_n+f_{n-1}-1。
为什么？我们拆！
\begin{aligned}
f_n &= f_{n-1}+f_{n-2} \\
&= f_{n-2}+f_{n-2}+f_{n-3} \\
&= f_{n-2}+f_{n-3}+f_{n-3}+f_{n-4} \\
&= \dots \\
&= f_{n-2}+f_{n-3}+\dots+f_{3}+f_{3}+f_{2} \\
&= f_{n-2}+f_{n-3}+\dots+f_{3}+f_{2}+f_{2}+f_{1} \\
&= f_{n-2}+\dots+f_{2}+f_{1}+{\color{red}f_{2}} \\
&= s_{n-2}+{\color{red}1}
\end{aligned}
所以 s_n=2\times f_n+f_{n-1}-1=s_{n-2}+1+f_{n-1}+f_{n}-1。
好的这是偷懒者，真是个好方法！
我们考虑普通人的解：
我们有一个目标矩阵：
\begin{bmatrix}
F_{n+1} & F_{n} & S_{n}
\end{bmatrix}
我们一开始有一个初始的矩阵：
\begin{bmatrix}
F_2 & F_{1} & S_{1}
\end{bmatrix}=
\begin{bmatrix}
1 & 1 & 1
\end{bmatrix}
那么我们推一下目标矩阵：
\text{Base}=\begin{bmatrix}
1 & 1 & ? \\
1 & 0 & ? \\
? & ? & ?
\end{bmatrix}
首先，我们发现求 F 不需要 S 参与，所以：
\text{Base}=\begin{bmatrix}
1 & 1 & ? \\
1 & 0 & ? \\
{\color{gold}0} & {\color{gold}0} & ?
\end{bmatrix}
然后，我们需要一个 S_{n-1} 和一个 F_{n}，推出 S_{n}，相当于：S_{n}=1\times F_{n}+0\times F_{n-1}+1\times S_{n-1} 所以：
\text{Base}=\begin{bmatrix}
1 & 1 & {\color{gold}1} \\
1 & 0 & {\color{gold}0} \\
0 & 0 & {\color{gold}1}
\end{bmatrix}
这样，你就独立完成了推理。
图上路径数（迷路弱化版）
就是给你一个图，要求 u 到 v 的路上正好 k 条的路径数。
我们定义一个状态：f_{i} 表示结束到 i 点的路径数。
每一次矩阵乘法，都是对矩阵迭代的一次，那么具体 \text{Base} 怎么写呢？
我们注意到每一条边，都将是一个有效迭代，所以 \text{Base}_{uv} 就是边数。
有点过于简单了。
啊不对我怎么跑了 1000ms+，好慢。我们可以发现这个矩阵是稀疏矩阵。 然后我们直接用专属优化即可，即枚举顺序 i\to k\to j，其中一旦找到 a_{i,k}=0，就停止。我们就这样优化到了 250ms+。
CF1117D
为什么题目那么多 xht37 /jy
就是你每一次可以加 1 个或 m 个宝石，然后求出恰好有 n 个宝石的方案数。
容易列出
f_i=\begin{cases}
1 & {i=0} \\
0 & {0<i<m}\\
f_{i-1}+f_{i-m} & {i\ge m}
\end{cases}
的转移式子 XD，然后直接做。
对应的，我们可以推出所有 \text{A}_{ii}=1。
然后所有 $\text{Base}_{i+1,i}=1$。
结束！（？）