假设矩阵为上三角矩阵，那么我们的枚举顺序可以优化：
这是原来的： F O R ( i , 1 , n ) F O R ( j , 1 , n ) F O R ( k , 1 , n ) FOR(i,1,n)FOR(j,1,n)FOR(k,1,n) FOR(i,1,n)FOR(j,1,n)FOR(k,1,n)
现在： F O R ( i , 1 , n ) F O R ( j , i , n ) F O R ( k , i , j ) FOR(i,1,n)FOR(j,i,n)FOR(k,i,j) FOR(i,1,n)FOR(j,i,n)FOR(k,i,j)
1 6 frac{1}{6} 61的常数优化，很给力。
2、答案的向量优化。多次题目的时候，矩阵快速幂的时间复杂度为 O ( T n 3 l o g n ) O(Tn^3logn) O(Tn3logn)
当矩阵固定时：
如果答案为一个行向量，则预处理 2 i 2^i 2i次幂。由于矩阵的结合律，我们可以维护该行向量，这样只需要 O ( n 2 l o g n ) O(n^2logn) O(n2logn)做一次回答。
3、累加贡献的矩阵。如果是矩阵前缀和的形式： ∑ i = 1 n B i sum_{i=1}^n B^i ∑i=1nBi ，可以把矩阵扩域达到此目的。
构造方法如下：
构造 T = { A I 0 I } T=egin{Bmatrix} A&I\ 0&I end{Bmatrix} T={A0II}
此时 T T T做 n + 1 n+1 n+1次前缀和，右上角的元素即为前缀和。
拓展：
右上角的 I I I可以换成列向量。
的话累计贡献就变成了相应的值。
典型例题：【清华集训】恐怖的奴隶主。
对于一个列向量 [ p 1 , p 2... p n ] [p1,p2...pn] [p1,p2...pn]表示状态为 1.. n 1..n 1..n时的贡献，则顺次相乘的累计结果恰好就是一次矩乘的贡献。
二、一些矩阵操作 矩阵的行列式∣ A ∣ = ∑ P ( − 1 ) d ( P ) ∏ i = 1 n A [ i ] [ p i ] |A|=sum_{P}(-1)^{d(P)}prod_{i=1}^n{A[i][pi]} ∣A∣=∑P(−1)d(P)∏i=1nA[i][pi]
d ( P ) d(P) d(P)为逆序对数。
一个神奇性质： ∣ A B ∣ = ∣ A ∣ ∣ B ∣ |AB|=|A||B| ∣AB∣=∣A∣∣B∣
逆矩阵A可逆
∣ A ∣ ≠ 0 |A|≠0 ∣A∣=0
r ( A ) = n r(A) = n r(A)=n
齐次线性方程组 A X = 0 AX=0 AX=0 仅有零解
非齐次线性方程组$AX=b $有唯一解
A的特征值不为0
矩阵的迹： t r ( A ) tr(A) tr(A)主对角线元素和。
方程如果存在0系数行，常数项 > 0 >0 >0，则方程无解。
否则方程有无数解。
矩阵的秩： r ( A ) r(A) r(A)表示线性无关的横行的极大数目。
齐次线性方程组常数项全为 0 0 0的方程组。
若 r ( A ) < n r(A)