矩阵学习笔记
Bryan1676
·
·
算法·理论
矩阵学习笔记
基本知识
定义
由 m \times n 个数 a_{i,j} 排成的 m 行 n 列的数表称为 m 行 n 列的矩阵，简称 m \times n 矩阵。记作（以三乘三矩阵为例）：
A=\begin{vmatrix}
a_{11}& a_{12} & a_{13}\\
a_{21}& a_{22} & a_{23}\\
a_{31} & a_{32} & a_{33}
\end{vmatrix}
矩阵乘法
对于两个 n \times m 与 m \times k 矩阵 A，B 定义它们相乘的结果是一个 n \times k 矩阵 C，且有 c_{i,j}=\sum_{x=1}^m a_{i,x}b_{x,j}。
对于一个 n\times n 的矩阵与一个 n\times 1 的矩阵的矩阵乘法，可以视作对于 n \times 1 矩阵中元素的一种变换，例如：
\begin{vmatrix}
0 & 1\\
1 &1
\end{vmatrix}
\begin{vmatrix}
f_{i-1}\\
f_i
\end{vmatrix}
=
\begin{vmatrix}
f_i \\
f_{i+1}
\end{vmatrix}
这也是斐波那契数列的递推，基于结合律可以使用快速幂加速。
矩阵乘法具有结合律，但不具有交换律，读者自证不难。
基矩阵/单位矩阵
定义：与任意矩阵基矩阵相乘后不变。
形状：（显然为 n \times n 矩阵）
\forall i \in [1,n],a_{i,i}=1 \\
\forall i \ne j \in [1,n],a_{i,j}=0
热身
T1 P1939 矩阵加速（数列）
显然的，我们有：
\begin{vmatrix}
0 & 1 &0 \\
0 & 0 &1 \\
1 & 0 & 1
\end{vmatrix}
\begin{vmatrix}
f_{i-2} \\
f_{i-1} \\
f_i
\end{vmatrix}
=
\begin{vmatrix}
f_{i-1} \\
f_i \\
f_{i+1}
\end{vmatrix}
直接快速幂加速即可，复杂度 \mathcal O(t\log n)。
矩阵变形-“+ max”矩阵
其余定义同常规矩阵，乘法的定义改为 c_{i,j}=\max_{x=1}^m a_{i,x}+b_{x,j}。
显然的，此时的矩阵乘法具有结合律，但不具有交换律。
“+ max”矩阵的基矩阵为：
\forall i \in [1,n],a_{i,i}=0 \\
\forall i \ne j \in [1,n],a_{i,j}=-\infty
线段树维护矩阵
由于矩阵乘法有一种“变幻”的性质，所以可以将线段树每个节点上拥有的数值视作一个 n \times 1 的向量（可以理解为一种特殊的只有 1 列的矩阵），每次操作就是给这个向量乘上一个变幻矩阵，用 lazy-tag 维护。下面是一些例题。
T2 【模板】线段树 2
考虑给每个线段树维护 sum 对于每种操作，有（上乘下加）：
sum \leftarrow sum*v \\
sum \leftarrow sum+(v*len)
因此还要维护一个辅助变量 len 在向量中。
实现上，对于每个节点，维护向量:
\begin{vmatrix}
sum \\
len
\end{vmatrix}
对于每次加操作，给对应节点的向量与懒标记乘上矩阵：
\begin{vmatrix}
1 & x \\
0 & 1
\end{vmatrix}
容易发现这是对的。
对于每次乘操作，给对应节点的向量与懒标记乘上矩阵：
\begin{vmatrix}
x & 0 \\
0 & 1
\end{vmatrix}
下传时将每个节点的懒标记乘到子节点的向量与懒标记上，然后将懒标记重置为单位矩阵即可。
T3 [NOIP2022] 比赛
标记定义
$maxb(l,r)$ 数列b在[l,r]内的最大值。\
在复杂度中默认$n$与$q$同阶。\
单位矩阵：对角线全为1，其他地方全为0的矩阵。
#### 题目大意
给定数列$a_{1-n},b_{1-n}$,每次询问l,r,询问:
$$ \sum ^r_{p=l} \sum ^r_{q=p} maxa(p,q)*maxb(p,q)$$
#### 转化
考虑离线，从 $1$ 至 $n$ 扫描 $r$ ，求解 $l$。
对于确定的r,我们先来考虑 $ \sum_{i=l}^rmaxa(i,r) * maxb(i,r)
如何求解
显然，这个式子可以用线段树维护，我们只需单调栈处理 a 与 b 最大值的变化，即可做到 O(nlogn) 的更新，但此时我们的查询却变成了 O(n^2logn)，因此就需要用线段树去维护区间历史所有版本的和
如何维护历史和
我们在线段树的节点上新增一个 hisab_u 表示u节点上的历史和，但不难发现这个东西用常规手法很难维护（你也可以暴力维护一堆懒标记，但我懒得去讨论了），我们先来考虑一维的历史和如何维护
Part1 一维历史和
对于线段树的每个节点，维护向量val
\begin{vmatrix}
hsum \\
sum \\
len \\
\end{vmatrix}
表示（从上到下）历史和，和，长度，区间修改时，记修改量为\Delta，即将区间的val乘上矩阵：
\begin{vmatrix}
1&0&0 \\
0&1&\Delta \\
0&0&1 \\
\end{vmatrix}
每轮更新结束后，将所有数的向量val乘上矩阵：
\begin{vmatrix}
1&1&0 \\
0&1&0 \\
0&0&1 \\
\end{vmatrix}
即可更新hsum。
这个东西可以开一颗线段树来维护每个节点的向量 val ,再记 tag_u 为节点 u 未下传的矩阵，下传时，将儿子的 tag 和 val 乘上父亲的 tag 然后将父亲的 tag 赋值为单位矩阵即可。
Part 2二维历史和
和上面一样，定义 val_u=
\begin{vmatrix}
hsum \\
sumab \\
suma\\
sumb\\
len \\
\end{vmatrix}
更新a时，记变化量为 \Delta_a,直接将 val 乘上：
\begin{vmatrix}
1&0&0&0&0 \\
0&1&0&\Delta_a&0 \\
0&0&1&0&\Delta_a \\
0&0&0&1&0 \\
0&0&0&0&1
\end{vmatrix}
更新 b 时同理。
对于上传，每轮更新结束后，给 [1,n] 的 val 乘上：
\begin{vmatrix}
1&1&0&0&0 \\
0&1&0&0&0 \\
0&0&1&0&0 \\
0&0&0&1&0 \\
0&0&0&0&1
\end{vmatrix}
即可，维护方法同上，查询时直接查询 hsum[l,r]，
复杂度为 \mathcal O(k^3nlogn) k=5。
常数优化
Part 1:基于矩阵性质的优化
注意到只有对角线上方有数，因此可以只维护对角线上方的数，这样可以将乘法次数从125优化到35次。
Part 2:线段树上的优化
注意到任何向量或矩阵乘上单位矩阵结果都不变，所以记 state_u 为u位置的 tag 是否是单位矩阵，只有 state_u=1 时 pushdown 时要去计算。
T4『STA - R4』冰红茶题解
标记含义
$\text{max1}$：节点对应的区间内最后连续和原味冰红茶瓶数最多的 bot 喝的冰红茶的瓶数。
$\text{max2}$：节点对应的区间内最后连续和热带风味冰红茶瓶数最多的 bot 喝的冰红茶的瓶数。
#### 思路
对于每个线段树上的点，记录向量 $$\text{val} =\begin{vmatrix}\text{sum}\\\text{max1}\\\text{max}2\\1\end{vmatrix}$$。
考虑怎么去更新。
##### Part I 喝冰红茶
这里只讨论和原味冰红茶的情况，热带风味冰红茶也是同理。
对于一个区间的 bot，喝下 $\text{k}$ 瓶原味冰红茶后，$\text{max1} \leftarrow \text{max1}+\text{k}，\text{max2} \leftarrow 0$，$\text{sum}$ 不变。
所以，我们可以直接给这个区间的 $\text{val}$ 乘上矩阵：
$$
\begin{vmatrix}
1&0&0&0\\
0&1&0&\text{k}\\
0&0&0&0\\
0&0&0&1
\end{vmatrix}$$
这部分可以用线段树维护。
##### Part II 击毁 bot
对于一个线段树节点，如果这个节点的 $\text{sum}$ 为 $0$ 或 $\max(\text{max1},\text{max2}) < \text{k}$，直接返回，否则递归处理左右儿子。
对于需要修改的叶子节点，将它的 $\text{val}$ 改为 $$\begin{pmatrix}0\\-\infty\\-\infty\\1\end{pmatrix}$$。
在 pushdown 时，不下传 $\text{sum}=0$ 区间的懒标记。
#### Part III 查询答案
最简单的一部分，直接输出 $\text{sum}_1$ 即可。
#### 复杂度分析
以下分析忽略矩阵乘法的常数。
对于喝冰红茶，显然是 $\mathcal O(n\log n)$的。
对于击毁 bot，我们发现每个 bot 只会被访问一次，因此对于每个 bot 的均摊复杂度是 $\mathcal O(\log n)$ 的，因此总复杂度为 $\mathcal O(n\log n)$。
综上，本题复杂度为 $\mathcal O(n\log n)$。
#### 常数优化
同上题。
### T5 P4314 CPU 监控
维护区间历史最大值，考虑在向量中维护 $hismax$ 表示历史最大值，考虑怎么更新，自然的想到用 “+ max” 矩阵，然后就做完了。
### T6 [THUSC 2017] 大魔法师
比较经典，留作习题答案略。
### T7 [Ynoi2009] rprmq1
发现每次区间加可以转换成在 $l1$ 时刻给 $l2$ 到 $r2$ 加上 $x$，然后在 $l2+1$ 时刻给 $l2$ 到 $r2$ 减去 $x$，查询区间最大值等价于查询 $l1$ 到 $r1$ 时刻的 $l2$ 到 $r2$ 的历史最大值。
考虑线段树对时间轴分治，每个询问的 $l1$ 到 $r1$ 拆成若干个小区间。复杂度 $\mathcal O(n\log^2n)$。
## 矩阵优化 dp
### T8【模板】动态 DP
首先有一个很 native 的线性 dp，记 $f_{u,0/1}$ 表示 $u$ 取或不取它的子树中的最大独立集。转移是简单的：
$$
f_{u,0}=\sum_{v \in son_u}\max(f_{v,0},f_{v,1}) \\
f_{u,1}=\sum_{v \in son_u} f_{v,0}
$$
考虑如何优化转移，定义状态 $g_{u,0/1}$ 表示 $u$ 取或不取它的轻儿子子树的最大独立集。
有:
$$
f_{u.0}=\max(f_{son_u,0},f_{son_u,1})+g_{u,0} \\
f_{u,1}=f_{son_u,0}+g_{u,1} \\
g_{u,0}=\sum_{v \in lightson_u}\max(f_{v,0},f_{v,1}) \\
g_{u,1}=\sum_{v \in lightson_u} f_{v,0}
$$
不难看出：
$$
\begin{vmatrix}
g_{u,0} & g_{u,0}\\
g_{u,1} & -\infty
\end{vmatrix}
\begin{vmatrix}
f_{son_u,0} \\
f_{son_u,1}
\end{vmatrix}=
\begin{vmatrix}
f_{u,0} \\
f_{u,1}
\end{vmatrix}
$$
因此，每个点的 $f$ 可以由从它重链底部的 $g$ 矩阵一直乘到它的 $g$ 矩阵来获得（对于叶子节点，$f_{u,0/1}=g_{u,0/1}$）。此处使用线段树维护矩阵乘积，每个点与它重链底部的点在 dfn 序上是一段连续的区间。
此外，还能发现每个点的修改，只会更改 $\log$ 个点的 $g$。
因此考虑找到这些点，分别求出他们变化前后 $g$ 的变化，然后暴力维护即可。
### T9 [NOIP 2018 提高组] 保卫王国
首先有一个显然的结论：
最小权覆盖=总权值-最大独立集。
考虑取最大独立集的补集即可证明。
对于强制选/不选，可以通过更换权值至 $\infty$ 或 $-\infty$ 来解决，然后就是动态 dp 板子题了。
### T10 New Year and Old Subsequence
考虑暴力的 dp，记 $f_{i,0/1/2/3/4}$ 表示目前考虑到点 $i$，已有子序列 $\emptyset,2,20,201,2017$ 的最少删除次数（转移见代码）。
发现可以用矩阵转移，甚至是静态的，直接线段树维护 “+ max”矩阵即可，复杂度 $\mathcal O(n+qlogn)$。
有不懂的可以在讨论区问我。