矩阵 0.矩阵# 既然讲矩阵就没必要讲向量了吧
定义一个形如 A = [ a 1 , 1 a 1 , 2 … a 1 , n a 2 , 1 a 2 , 2 … a 2 , n ⋮ ⋮ ⋱ ⋮ a m , 1 a m , 2 … a m , n ] A = \begin{bmatrix} a _ {1,1} & a _ {1,2} & \ldots & a _ {1,n} a _ {2,1} & a _ {2,2} & \ldots & a _ {2,n} \vdots & \vdots & \ddots & \vdots a _ {m,1} & a _ {m,2} & \ldots & a _ {m,n} \end{bmatrix} A = [ a 1 , 1 a 1 , 2 … a 1 , n a 2 , 1 a 2 , 2 … a 2 , n ⋮ ⋮ ⋱ ⋮ a m , 1 a m , 2 … a m , n ] n n n m m m
设 A , B , C A,B,C A , B , C n × m n \times m n × m D D D m × k m \times k m × k E E E n × k n \times k n × k
A ± B = [ a 1 , 1 ± b 1 , 1 a 1 , 2 ± b 1 , 2 … a 1 , n ± b 1 , n a 2 , 1 ± b 2 , 1 a 2 , 2 ± b 2 , 2 … a 2 , n ± a 2 , n ⋮ ⋮ ⋱ ⋮ a m , 1 ± b m , 1 a m , 2 ± b m , 2 … a m , n ± b m , n ] E = C D , E i , j = ∑ l = 1 m C i , l D l , j A \pm B = \begin{bmatrix} a _ {1,1} \pm b _ {1,1} & a _ {1,2} \pm b _ {1,2} & \ldots & a _ {1,n} \pm b _ {1,n} a _ {2,1} \pm b _ {2,1} & a _ {2,2} \pm b _ {2,2} & \ldots & a _ {2,n} \pm a _ {2,n} \vdots & \vdots & \ddots & \vdots a _ {m,1} \pm b _ {m,1} & a _ {m,2} \pm b _ {m,2} & \ldots & a _ {m,n} \pm b _ {m,n} \end{bmatrix} E = CD,E _ {i,j} = \sum _ {l = 1} ^ m C _ {i,l} D _ {l,j} A ± B = [ a 1 , 1 ± b 1 , 1 a 1 , 2 ± b 1 , 2 … a 1 , n ± b 1 , n a 2 , 1 ± b 2 , 1 a 2 , 2 ± b 2 , 2 … a 2 , n ± a 2 , n ⋮ ⋮ ⋱ ⋮ a m , 1 ± b m , 1 a m , 2 ± b m , 2 … a m , n ± b m , n ] E = C D , E i , j = l = 1 ∑ m C i , l D l , j 其中，加减法满足交换律与结合律，乘法 仅满足结合律
加法单位元为零矩阵 O n , m = [ 0 0 … 0 ⋮ ⋮ ⋱ ⋮ 0 0 … 0 ] O _ {n,m} = \begin{bmatrix} 0 & 0 & \ldots & 0 \vdots & \vdots & \ddots & \vdots 0 & 0 & \ldots & 0 \end{bmatrix} O n , m = [ 0 0 … 0 ⋮ ⋮ ⋱ ⋮ 0 0 … 0 ] n = m n = m n = m I n = [ 1 0 … 00 1 … 0 ⋮ ⋮ ⋱ ⋮ 0 0 … 1 ] I _ n = \begin{bmatrix} 1 & 0 & \ldots & 0 0 & 1 & \ldots & 0 \vdots & \vdots & \ddots & \vdots 0 & 0 & \ldots & 1 \end{bmatrix} I n = [ 1 0 … 00 1 … 0 ⋮ ⋮ ⋱ ⋮ 0 0 … 1 ]
与群相关# 矩阵运算结果仍是矩阵，满足封闭性，还满足结合律，两个运算均有单位元与逆元，设所有矩阵的集合为 M M M G ( M , + , × ) G(M,+,\times) G ( M , + , × )
你甚至可以用线段树来维护这东西
矩阵快速幂# 详见这里
矩阵求逆# 定义满足 A A − 1 = A − 1 A = I AA^ {-1} = A ^ {-1}A = I A A − 1 = A − 1 A = I A − 1 A ^ {-1} A − 1 A A A
由逆元的性质得，这玩意可以当作矩阵的“除法”。
但是，这个东西不一定存在，存在的充要条件如下:
B B B n n n A x = B Ax = B A x = B A A A 求矩阵逆可以用高斯消元法，但我更喜欢用 Gauss-Jordan 消元法，它的目的是将原矩阵化为单位矩阵。
线性方程组求解# 任一线性方程组都能被写成 A X = B AX = B A X = B A A A X , B X,B X , B
回忆我们解方程组的过程，用到了加减消元和代入消元，并且只会操作系数，所以我们可以把系数全部提取出来，单独进行计算。
具体的，就是把 A , B A,B A , B [ A B ] \begin{bmatrix} A & B \end{bmatrix} [ A B ]
Gauss-Jordan 消元是这样的：先选取每一列绝对值最大的当作主元，然后进行对换变换，再将主元化为 1 1 1 0 0 0
逆矩阵的定义是 A A − 1 = I AA ^ {-1} = I A A − 1 = I [ A I ] \begin{bmatrix} A & I \end{bmatrix} [ A I ] [ I A − 1 ] \begin{bmatrix} I & A ^ {-1} \end{bmatrix} [ I A − 1 ]
1.在 OI 中的应用# 优化 DP# 有些 DP 的转移可以被抽象成群上的运算，并且是类似 O P T k = 1 n A i , k o p t B k , j OPT _ {k = 1} ^ nA _ {i,k} opt B _ {k,j} OP T k = 1 n A i , k o pt B k , j O ( n ) \Omicron(n) O ( n ) O ( log n ) \Omicron(\log n) O ( log n )
为此，我们可以定义广义矩阵乘法。本质上就是群上的一个二元运算，前提是该运算具有结合律。
比如这道 ，可以定义 C = A × B , C i , j = min k = 1 n A i , k + B k , j C = A \times B,C _ {i,j} = \min _ {k = 1} ^ nA _ {i,k} + B _ {k,j} C = A × B , C i , j = min k = 1 n A i , k + B k , j
动态 DP 中，广义矩阵乘法很常用。
连通性邻接矩阵的幂的意义之前写过了 。
Tricks# 1.拆点# 因为连通性邻接矩阵只能存 0/1 （或者有重边可以更多），而有些题是带边权并且一般很小。这个时候我们就可以拆点，把 u u u ( u 1 , u 2 , … , u W ) (u _ 1,u _ 2,\ldots,u _ W) ( u 1 , u 2 , … , u W ) ∀ i ∈ [ 1 , W ) , u i + 1 \forall i \in [1,W), u _ {i + 1} ∀ i ∈ [ 1 , W ) , u i + 1 u i u _ i u i u u u v v v w w w u 1 u _ 1 u 1 v w v _ w v w
2.点边互换# 在这道题 中，需要记录边的状态而非点的状态。这个时候我们可以考虑用边来当作状态。
设 d p i , j dp _ {i,j} d p i , j a a a i i i j j j d p i , j = ∑ u ∈ E i d p u , j − 1 dp _ {i,j} = \sum _ {u \in E _ i} dp _ {u,j - 1} d p i , j = ∑ u ∈ E i d p u , j − 1 E i E _ i E i i i i
然后可以将第二维滚掉，用矩阵快速幂优化。设 F F F B B B A n s = F B t − 1 Ans = FB ^ {t - 1} A n s = F B t − 1 ∑ i ∈ E b A n s i \sum _ {i \in E _ b} Ans _ i ∑ i ∈ E b A n s i
