矩阵
Linzijian2012
·
2024-07-30 16:03:15
·
算法·理论
前言
内容有违反洛谷社区规则的或不规范的，请私信本蒟蒻或直接发在评论区。
以下数组、矩阵下标均从 \mathbf1 开始。无特殊说明，变量默认为正整数。
正文
1 矩阵基础知识
矩阵，简单来说就是把一堆数排成矩形（也就是长方形）的样子。在 OI 中，常用二维数组存储它。下文中，对于一个有 n 行、m 列的矩阵，会用 n\ast m 表示。实际上，更多情况下，使用的是 n\times m 。但是这里作为区分，使用了 n\ast m 。对于矩阵 A 第 i 行第 j 列的元素，令它为 A_{i,j} 。那么，一个矩阵就可以这样表示：
A=\begin{bmatrix}A_{1,1}&A_{1,2}&\cdots&A_{1,m}\\A_{2,1}&A_{2,2}&\cdots&A_{2,m}\\\vdots&\vdots&\ddots&\vdots\\A_{n,1}&A_{n,2}&\cdots&A_{n,m}\end{bmatrix}
若有 n_1\ast m_1 的矩阵 A ，与 n_2\ast m_2 的矩阵 B ，则：(n_1=n_2)\wedge(m_1=m_2)\wedge(\forall1\le i\le n_1,1\le j\le m_1,A_{i,j}=B_{i,j})\Leftrightarrow A=B 。下面先讨论矩阵加法 和矩阵减法 。对于 n\ast m 的矩阵 A 和 n\ast m 的矩阵 B ，它们的和与差也是一个 n\ast m 的矩阵（记为 C ）。具体来说：
\begin{array}{l}\quad A\pm B\\=C\\=\begin{bmatrix}A_{1,1}\pm B_{1,1}&A_{1,2}\pm B_{1,2}&\cdots&A_{1,m}\pm B_{1,m}\\A_{2,1}\pm B_{2,1}&A_{2,2}\pm B_{2,2}&\cdots&A_{2,m}\pm B_{2,m}\\\vdots&\vdots&\ddots&\vdots\\A_{n,1}\pm B_{n,1}&A_{n,2}\pm B_{n,2}&\cdots&A_{n,m}\pm B_{n,m}\end{bmatrix}\end{array}\\A\pm B=C\\\Downarrow\\C_{i,j}=A_{i,j}\pm B_{i,j}(1\le i\le n,1\le j\le m)
对于数的加法，有两条定律：
交换律，a+b=b+a
结合律，(a+b)+c=a+(b+c)
矩阵也满足上面的性质。
交换律：设 C=A+B ，A 、B 均为 n\ast m 的矩阵。
\begin{array}{l}\because C=A+B\\\therefore C_{i,j}=A_{i,j}+B_{i,j}(1\le i\le n,1\le j\le m)\\\therefore C_{i,j}=B_{i,j}+A_{i,j}\\\therefore C=B+A\\\therefore A+B=B+A\end{array}
结合律：设 A 、B 、C 均为 n\ast m 的矩阵，D=A+B ，E=B+C ，F=D+C=(A+B)+C ，G=A+E=A+(B+C) 。
\begin{array}{l}\because D=A+B,E=B+C\\\therefore D_{i,j}=A_{i,j}+B_{i,j}(1\le i\le n,1\le j\le m)\\\;\;\,\,E_{i,j}=B_{i,j}+C_{i,j}(1\le i\le n,1\le j\le m)\\\because F=D+C\\\therefore F_{i,j}=D_{i,j}+C_{i,j}(1\le i\le n,1\le j\le m)\\\qquad\quad\;\;\;A_{i,j}+B_{i,j}+C_{i,j}\\\because G=A+E\\\therefore G_{i,j}=A_{i,j}+E_{i,j}(1\le i\le n,1\le j\le m)\\\qquad\quad\;\;\;\;\;\!\!\!A_{i,j}+B_{i,j}+C_{i,j}\\\therefore\forall1\le i\le n,1\le j\le m, F_{i,j}=G_{i,j}\\\therefore F=G\\\therefore(A+B)+C=A+(B+C)\end{array}
这就是矩阵的基本知识，更重要的在于矩阵乘法 。
2 矩阵乘法
直接上定义：对于 n\ast m 的矩阵 A ，和 m\ast p 的矩阵 B ，它们的乘积是一个 n\ast p 的矩阵 C 。具体来说：
\forall1\le i\le n,1\le j\le p,C_{i,j}=\sum_{k=1}^mA_{i,k}\times B_{k,j}
从这个式子也可以看出：A 矩阵的行数必须等于 B 矩阵的列数。
对于数的乘法，有三个性质：
交换律，a\times b=b\times a
结合律，(a\times b)\times c=a\times(b\times c)
分配律，a\times(b+c)=a\times b+a\times c
对于乘法分配律，这里不做讨论。很明显，矩阵不满足乘法交换律 ，因为当 n\ne p 时，这两个矩阵甚至没法乘在一起。但是，矩阵满足乘法结合律 ，下面给出证明：
设 A 为 n\ast m 的矩阵，B 为 m\ast p 的矩阵，C 为 p\ast q 的矩阵，D=A\times B ，E=B\times C 。易知 D 为 n\ast p 的矩阵，E 为 m\ast q 的矩阵。令 F=D\times C=(A\times B)\times C ，G=A\times E=A\times(B\times C) 。易知 F 为 n\ast q 的矩阵，G 也为 n\ast q 的矩阵。
\begin{array}{l}\because n=n,q=q\\\therefore \forall1\le i\le n,1\le j\le q,F_{i,j}=G_{i,j}\Leftrightarrow F=G\\\because D=A\times B\\\therefore\forall1\le i\le n,1\le j\le p,D_{i,j}=\displaystyle\sum_{x=1}^mA_{i,x}\times B_{x,j}\\\because E=B\times C\\\therefore\forall1\le i\le m,1\le j\le q,E_{i,j}=\displaystyle\sum_{y=1}^pB_{i,y}\times C_{y,j}\\\because F=D\times C\\\therefore\forall1\le i\le n,1\le j\le q,F_{i,j}=\displaystyle\sum_{y=1}^pD_{i,y}\times C_{y,j}\\\quad=\displaystyle\sum_{y=1}^p\left(\sum_{x=1}^mA_{i,x}\times B_{x,y}\right)\times C_{y,j}\\\quad=\displaystyle\sum_{y=1}^p\sum_{x=1}^m\big(A_{i,x}\times B_{x,y}\times C_{y,j}\big)\\\quad=\displaystyle\sum_{x=1}^m\sum_{y=1}^p\big(A_{i,x}\times B_{x,y}\times C_{y,j}\big)\\\because G=A\times E\\\therefore\forall1\le i\le n,1\le j\le q,G_{i,j}=\displaystyle\sum_{x=1}^mA_{i,x}\times E_{x,j}\\\quad=\displaystyle\sum_{x=1}^mA_{i,x}\times\left(\sum_{y=1}^pB_{x,y}\times C_{y,j}\right)\\\quad=\displaystyle\sum_{x=1}^m\sum_{y=1}^p\big(A_{i,x}\times B_{x,y}\times C_{y,j}\big)\\\therefore\forall1\le i\le n,1\le j\le q,F_{i,j}=G_{i,j}\\\therefore F=G\\\therefore(A\times B)\times C=A\times(B\times C)\end{array}
容易看出，矩阵乘法是 O(n\times m\times p) 的算法，一般情况下，时间复杂度都看作 O(n^3) 。
到这里，矩阵乘法就讲完了。接着，我们要接触到矩阵乘法带来的快捷——矩阵快速幂 。
3 矩阵快速幂
下文中，记 \begin{matrix}\underbrace{A\times A\times\cdots\times A}\\k\end{matrix} 为 A^k ，其中 A 为 n\ast n 的矩阵 。
假设现在有一个 A 矩阵，它有 n 行 n 列。请计算 A^k 的结果，对 998244353 取模，1\le n\le100 ，1\le k\le10^{18} 。
如果 A 是一个数，就会简单很多：直接用快速幂就行，时间复杂度 O(\log k) ，快到飞起，轻松 AC。但是现在 A 是一个矩阵，唯一可以利用的就是“矩阵满足结合律 ”这条性质。让我们先来回顾一下，普通的快速幂算法的原理 是什么。
假设现在想要计算 x^k ，则令 m=\log_2k+1 ，d_i=\displaystyle\left\lfloor\frac k{2^i}\right\rfloor\bmod2(0\le i<m) ，故：
k=\sum_{i=0}^{m-1}2^i\times d_i\\\begin{aligned}x^k&=x^{\sum_{i=0}^{m-1}2^i\times d_i}\\&=\prod_{i=0}^{m-1}x^{2^i\times d_i}\end{aligned}
在这个式子中，外层的累乘复杂度为 O(\log k) ，里面可以实时维护，所以计算 x^k 的时间复杂度为 O(\log k) 。但是这么算的本质，其实是利用了乘法结合律 。只要把累乘、累和式展开：
\begin{aligned}x^k&=\begin{matrix}\underbrace{x\times x\times\cdots\times x}\\k\end{matrix}\\&=\begin{matrix}\underbrace{x\times x\times\cdots\times x}\\2_0\times d_0+2^1\times d_1+\cdots+2^{m-1}\times d_{m-1}\end{matrix}\\&=\begin{matrix}\underbrace{(x\times x\times\cdots\times x)}\\2^0\times d_0\end{matrix}\times\begin{matrix}\underbrace{(x\times x\times\cdots\times x)}\\2^1\times d_1\end{matrix}\times\cdots\times\begin{matrix}\underbrace{(x\times x\times\cdots\times x)}\\2^{m-1}\times d_{m-1}\end{matrix}\end{aligned}
可以看出，快速幂利用的就是乘法结合律 。由此得出：虽然现在 A 是一个矩阵，但是因为它满足结合律，所以也可以用快速幂计算，时间复杂度为 O(n^3\log k) ，其中 n^3 是矩阵乘法的复杂度。
事实上，很多利用矩阵加速的题，时间复杂度都是 O(n^3\log k) 。下面就来看几道例题。
4 一般矩阵加速优化 dp
需要矩阵加速的题目都有一个特点：有一个变量可以很大（比如 10^9 、10^{12} 、10^{18} ），而其他的变量一般都很小（比如 10 、30 、50 ）。这种题基本要用到矩阵加速。这是因为矩阵加速的时间复杂度只有 O(n^3\log k) ，导致大变量（也就是 k ）经过 \log 运算之后只剩下几十。而小变量（也就是 n ）一般作为矩阵的大小，经过矩阵乘法的运算后，时间复杂度是 O(n^3) 级别，只能这么小。
然而，用矩阵加速优化 dp，或是矩阵求数列第 n 项的题目，都有一个要求：转移方程（递推式）的最高次数是一次 ，也就是不能出现 两个 dp 值（数列前面某两项的值）相乘 。因为这种情况下，矩阵是处理不了的。这是因为快速幂中的矩阵必须都一样 。如果里面的矩阵会变化，那就是另一回事了，因为矩阵快速幂没法优化它。所以，想要凑出两个递推值相乘，就需要“需要快速幂优化”的矩阵发生变化，然而它本身却不能变化，最终导致了不能使用矩阵加速。
4.1 例题 1：P4159 [SCOI2009] 迷路
见 P4159 题解。
4.2 例题 2：P2151 [SDOI2009] HH去散步
见 P2151 题解。
5 广义矩阵加速优化 dp
前面说是“一般”，是因为它还是利用原来的矩阵乘法。现在的“广义矩阵加速”则要自己动手定义，让矩阵加速能适用于更多的题目。
具体来说，如果有两个二元运算 \operatorname{op1} 和 \operatorname{op2} ，如 \min 和 + ，\max 和 \times ，等等。那么有以下结论：
如果有 \displaystyle\begin{cases}a\operatorname{op1}b=b\operatorname{op1}a\\(a\operatorname{op1}b)\operatorname{op1}c=a\operatorname{op1}(b\operatorname{op1}c)\\a\operatorname{op2}(b\operatorname{op1}c)=(a\operatorname{op2}b)\operatorname{op1}(a\operatorname{op2}c)\end{cases} ，那么就可以定义类矩阵乘法 C_{i,j}=(A_{i,1}\operatorname{op2}B_{1,j})\operatorname{op1}(A_{i,2}\operatorname{op2}B_{2,j})\operatorname{op1}\cdots\operatorname{op1}(A_{i,m}\operatorname{op2}B_{m,j}) ，这样的类矩阵乘法满足乘法交换律，其中 C=A\times B ，A 为 n\ast m 的类矩阵，B 为 m\ast p 的类矩阵，A 、B 、C 均为同一种类矩阵。
证明很简单。回想一下证明“矩阵满足乘法结合律”的过程，只是利用了和式的两个性质：
\displaystyle a\times\left(\sum_{i=l}^rb_i\right)=\sum_{i=l}^r\left(a\times b_i\right)
\displaystyle \sum_{i=l_1}^{r_1}\sum_{j=l_2}^{r_2}a_{i,j}=\sum_{j=l_2}^{r_2}\sum_{i=l_1}^{r_1}a_{i,j}
第 1 点本质是分配律 ，第 2 点本质是交换律、结合律 。所以就有上面的结论。
很明显，第一个例子可以创建类矩阵，而第二种不行，因为 -3\times\max\{-1,-2\}=3\ne\max\{-3\times(-1),-3\times(-2)\} 。我将第一种类矩阵成称为“M(\min,+) 矩阵”，而一般的矩阵在下文中可以写成 “M(+,\times) 矩阵”。
5.1 例题 1：[USACO07NOV] Cow Relays G
见 P2886 题解。
5.2 例题 2 [NOI Online #1 入门组] 魔法
见 P6190 题解。
附录
链接里面的“wa”指的是“Wonderful Article”（完美的文章）！
蒟蒻的其他专栏。