通过查询本喵的获奖记录可以看到，我只有 5 级钩，所以可能不会讲得很深，但应该不会出错。
一、矩阵定义
把若干个数字排成一个矩形表，就是 矩阵。
例如：
[abcd]\begin{bmatrix} a & b \\ c & d \end{bmatrix} [ac bd ]
通常记作：
A=(aij)m×nA=(a_{ij})_{m\times n} A=(aij )m×n
其中：
* mmm 表示行数；
* nnn 表示列数；
* aija_{ij}aij 表示第 iii 行第 jjj 列的元素。
二、常用概念
* 同型矩阵：行数 和 列数 都相等的 两个 矩阵。
* 方阵：行数 和 列数 都相等的 一个 矩阵。
* 零矩阵：所有元素都是 000 的矩阵，记作 OOO。
* 单位矩阵：主对角线全为 111、其余元素为 000 的方阵，记作 III。
> 主对角线是指从左上角到右下角的对角线。
三、矩阵的加减法
> 只有同型矩阵才可以进行加减运算，即两个矩阵的行数和列数分别相等。
运算规则：对应位置上的元素相加减。
例如：
[1324]+[5678]=[1+53+62+74+8]=[69912]\begin{bmatrix} 1 & 3 \\ 2 & 4 \end{bmatrix} + \begin{bmatrix} 5 & 6 \\ 7 & 8 \end{bmatrix} = \begin{bmatrix} 1+5 & 3+6 \\ 2+7 & 4+8 \end{bmatrix} = \begin{bmatrix} 6 & 9 \\ 9 & 12 \end{bmatrix} [12 34 ]+[57 68 ]=[1+52+7 3+64+8 ]=[69 912 ]
四、矩阵乘法
> 我觉得这部分最难了，也可能是本喵太菜了。
1. 乘法条件
若矩阵 AAA 是 m×nm\times nm×n 的矩阵，矩阵 BBB 是 n×pn\times pn×p 的矩阵，则它们可以相乘：
C=ABC=AB C=AB
结果 CCC 是一个 m×pm\times pm×p 的矩阵。
也就是说：
> AAA 的列数等于 BBB 的行数才可相乘（当然，把这句话反过来说，也就是“BBB 的行数等于 AAA 的列数”，意思是一样的喵）。
2. 乘法规则
接上条，设：
C=ABC=AB C=AB
则 CCC 的第 iii 行第 jjj 列的元素为：
cij=∑k=1naikbkjc_{ij}=\sum_{k=1}^{n} a_{ik}b_{kj} cij =k=1∑n aik bkj
用喵话说，就是：
> AAA 的第 iii 行与 BBB 的第 jjj 列的对应元素相乘后再相加。
例如：
A=[1234],B=[5678]A= \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}, \quad B= \begin{bmatrix} 5 & 6 \\ 7 & 8 \end{bmatrix} A=[13 24 ],B=[57 68 ]
计算 C=ABC=ABC=AB：
c11=1⋅5+2⋅7=19c_{11}=1\cdot 5+2\cdot 7=19 c11 =1⋅5+2⋅7=19
c12=1⋅6+2⋅8=22c_{12}=1\cdot 6+2\cdot 8=22 c12 =1⋅6+2⋅8=22
c21=3⋅5+4⋅7=43c_{21}=3\cdot 5+4\cdot 7=43 c21 =3⋅5+4⋅7=43
c22=3⋅6+4⋅8=50c_{22}=3\cdot 6+4\cdot 8=50 c22 =3⋅6+4⋅8=50
所以：
C=[19224350]C= \begin{bmatrix} 19 & 22 \\ 43 & 50 \end{bmatrix} C=[1943 2250 ]
3. 特殊性质
* 矩阵乘法不满足交换律，即 AB≠BAAB\neq BAAB=BA。
* 矩阵乘法满足结合律，即 (AB)C=A(BC)(AB)C=A(BC)(AB)C=A(BC)。
* 矩阵乘法满足分配律，即 A(B+C)=AB+ACA(B+C)=AB+ACA(B+C)=AB+AC。
五、方阵的幂
显然只有方阵才能自己乘自己。
定义：
Ak=AA⋯A⏟k 个A^k = \underbrace{A A \cdots A}_{k \text{ 个}} Ak=k 个AA⋯A
特别地，约定：
A0=IA^{0}=I A0=I
六、矩阵快速幂
矩阵快速幂和普通整数快速幂的思想完全一样：将指数按二进制拆分，利用幂的运算性质加速。
我们要计算 AbA^bAb，其中 AAA 是方阵。
如果直接乘 bbb 次，复杂度是 O(b⋅n3)O(b\cdot n^3)O(b⋅n3)，当 bbb 很大时不可接受。
快速幂做法：
把指数 bbb 写成二进制。例如：
b=13=11012b=13=1101_2 b=13=11012
那么：
A13=A8⋅A4⋅A1A^{13}=A^8 \cdot A^4 \cdot A^1 A13=A8⋅A4⋅A1
我们只需要维护一个底数 base=A2kbase=A^{2^k}base=A2k，每次让 basebasebase 自己乘自己，就能得到 A1,A2,A4,A8,⋯A^1,A^2,A^4,A^8,\cdotsA1,A2,A4,A8,⋯。
如果当前二进制位是 111，就把结果乘上这个 basebasebase。
算法流程
设结果矩阵 res=Ires=Ires=I，底数矩阵 base=Abase=Abase=A。
当 b>0b>0b>0 时：
1. 如果 bbb 的最低位是 111，则 res=res×baseres=res\times baseres=res×base；
2. 令 base=base×basebase=base\times basebase=base×base；
3. 令 b=b>>1b=b>>1b=b>>1。
最后 res=Abres=A^bres=Ab。
复杂度：一次矩阵乘法是 O(n3)O(n^3)O(n3)，快速幂需要乘 O(logb)O(\log b)O(logb) 次，总复杂度 O(n3logb)O(n^3\log b)O(n3logb)。
七、矩阵快速幂优化递推
> 终于到了喵。
例子：斐波那契数列
斐波那契数列的定义：
F0=0,F1=1F_0=0,\quad F_1=1 F0 =0,F1 =1
Fn=Fn−1+Fn−2F_n=F_{n-1}+F_{n-2} Fn =Fn−1 +Fn−2
直接递推求解显然为 O(n)O(n)O(n)，但可以使用今天的内容优化到 O(logn)O(\log n)O(logn)。
构造转移矩阵
我们把当前需要的两项打包成一个列向量：
vn=[FnFn−1]v_n= \begin{bmatrix} F_n\\ F_{n-1} \end{bmatrix} vn =[Fn Fn−1 ]
那么下一项：
vn+1=[Fn+1Fn]v_{n+1}= \begin{bmatrix} F_{n+1}\\ F_n \end{bmatrix} vn+1 =[Fn+1 Fn ]
观察：
Fn+1=1⋅Fn+1⋅Fn−1F_{n+1}=1\cdot F_n+1\cdot F_{n-1} Fn+1 =1⋅Fn +1⋅Fn−1
Fn=1⋅Fn+0⋅Fn−1F_n=1\cdot F_n+0\cdot F_{n-1} Fn =1⋅Fn +0⋅Fn−1
所以转移矩阵为：
M=[1110]M= \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix} M=[11 10 ]
于是：
vn+1=Mvnv_{n+1}=Mv_n vn+1 =Mvn
连续递推可得：
vk=Mkv0v_k=M^k v_0 vk =Mkv0
其中初始向量：
v0=[F1F0]=[10]v_0= \begin{bmatrix} F_1\\ F_0 \end{bmatrix} = \begin{bmatrix} 1\\ 0 \end{bmatrix} v0 =[F1 F0 ]=[10 ]
因此求 FkF_kFk ，只需计算 MkM^kMk，然后乘上 v0v_0v0 ，结果向量的第二行就是 FkF_kFk 。
另外，通过归纳法可以证明：
Mk=[Fk+1FkFkFk−1]M^k= \begin{bmatrix} F_{k+1} & F_k\\ F_k & F_{k-1} \end{bmatrix} Mk=[Fk+1 Fk Fk Fk−1 ]
所以也可以直接取 MkM^kMk 的第一行第二列。
一般二阶线性递推
如果递推形式是：
an=p⋅an−1+q⋅an−2a_n=p\cdot a_{n-1}+q\cdot a_{n-2} an =p⋅an−1 +q⋅an−2
同样把当前两项打包：
vn=[anan−1]v_n= \begin{bmatrix} a_n\\ a_{n-1} \end{bmatrix} vn =[an an−1 ]
那么：
an+1=p⋅an+q⋅an−1a_{n+1}=p\cdot a_n+q\cdot a_{n-1} an+1 =p⋅an +q⋅an−1
an=1⋅an+0⋅an−1a_n=1\cdot a_n+0\cdot a_{n-1} an =1⋅an +0⋅an−1
所以转移矩阵为：
M=[pq10]M= \begin{bmatrix} p & q\\ 1 & 0 \end{bmatrix} M=[p1 q0 ]
更高阶递推
若递推式涉及前 *** 项，则需要维护 *** 维列向量，转移矩阵为 d×dd\times dd×d，第一行放递推系数，下面各行负责把旧分量向下搬运。
例如递推式：
an=p⋅an−1+q⋅an−2+r⋅an−3a_n=p\cdot a_{n-1}+q\cdot a_{n-2}+r\cdot a_{n-3} an =p⋅an−1 +q⋅an−2 +r⋅an−3
转移矩阵为：
[pqr100010]\begin{bmatrix} p & q & r\\ 1 & 0 & 0\\ 0 & 1 & 0 \end{bmatrix} p10 q01 r00
规律非常明显喵。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
至此，矩阵快速幂优化递推的核心思想就讲完了。总结一下：
1. 确定状态向量；
2. 写出递推关系；
3. 构造转移矩阵；
4. 快速幂求解。
