基础知识
矩阵定义
晚点写。
矩阵加法/矩阵减法
晚点写
矩阵乘法
前置条件
矩阵乘法有意义，当且仅当第一个矩阵的列数和第二个矩阵的行数相同时。
则此时两个矩阵相乘的行数为第一个矩阵的行数，列数为第二个矩阵的列数。
可以记为将两个矩阵相同的一个边长去掉，然后第一个矩阵剩余的边长作为最终结果的行数，第二个矩阵剩余的边长作为最终结果的列数。
故设 $P$ 为 $a\times b$ 的矩阵，$Q$ 为 $b\times c$ 的矩阵。
设 $R$ 为矩阵 $P$ 与 $Q$ 的乘积，则大小为 $a\times c$。
运算法则
矩阵 $R$ 中的第 $i$ 行第 $j$ 列元素可以表示为
$$C_{i,j}=\sum\limits_{k=1}^{M}A_{i,k}\times B_{k,j}$$
一种可能的记忆方法
对于 $A$ 矩阵的第 $i$ 行，将其顺时针旋转 $90\degree$，并将其与 $B$ 矩阵的第 $j$ 列每个对应的数相乘，其和即为 $C_{i,j}$。
举个例子：
$A$ 为 $4\times6$ 的矩阵，$B$ 为 $6\times2$ 的矩阵，则 $C$ 为 $4\times2$ 的矩阵。
假设要求 $C_{3,2}$，则取出 $A$ 矩阵第 $3$ 行，将其顺时针旋转 $90\degree$，可得 $A'$。同时去除 $B$ 矩阵第二列，将 $A'$ 与 $B$ 第二列位于同一行的数乘起来，最后将所有乘积求和即得 $C_{3,2}$。
性质
矩阵乘法满足结合律，即 $(A\times B)\times C=A\times(B\times C)$。
矩阵乘法不满足交换律，即 $A\times B\not=B\times A$。
矩阵快速幂
由于矩阵满足结合律，所以可以对乘法的次数进行二进制拆分，那么就可以和普通的快速幂一样了。
需要注意的是，没有快速幂的目标矩阵 $A^0$ 应该是单位矩阵 $I$。
矩阵模板
1 | template<typename T> // T 表示矩阵存的值的类型 |
题目分析
矩阵 - 题单 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
矩阵乘法/【模板】矩阵快速幂
直接套用模板即可，无需多说。
矩阵加速（数列）
题意简述
已知一个数列 $a$，它满足：
$$ a_x= \begin{cases} 1 & x \in\{1,2,3\}\\ a_{x-1}+a_{x-3} & x \geq 4 \end{cases} $$
求 $a$ 数列的第 $n\,(1\le n\le2\times10^9)$ 项对 $10^9+7$ 取余的值。
算法分析
由于 $n$ 的范围较大，递推显然会 TLE，所以可以使用矩阵加速递推。
由于当前值 $a_x$ 与前三项值相关，故设计
$$
f(x-1)=
\begin{bmatrix}
a_{x-3}\\
a_{x-2}\\
a_{x-1}\\
\end{bmatrix}
,f(x)=
\begin{bmatrix}
a_{x-2}\\
a_{x-1}\\
a_{x}
\end{bmatrix}
$$
所以我们希望得到一个矩阵 $P$，使得 $P\times f(x-1)=f(x)$，然后进行转移。
$$
P\times
\begin{bmatrix}
a_{x-3}\\
a_{x-2}\\
a_{x-1}
\end{bmatrix}=
\begin{bmatrix}
a_{x-2}\\
a_{x-1}\\
a_{x}
\end{bmatrix}
$$
由于最终结果为 $3\times1$ 的矩阵，而一个乘矩阵为 $3\times1$，所以 $P$ 应为大小 $3\times3$ 的矩阵。
设第一行的数依次为 $i,j,k$，那么要使得 $i\times a_{x-3}+j\times a_{x-2}+k\times a_{x-1}=a_{x-2}$，那么显然 $i=k=0,j=1$。
同理，第二行依次为 $0,0,1$。
设第三行的数以此为 $y,z,w$，那么
$$
y\times a_{x-3}+z\times a_{x-2}+w\times a_{x-1}=a_{x}=a_{x-1}+a_{x-3}\,⇒\,y=1,z=0,w=1
$$
故
$$
P=
\begin{bmatrix}
0&1&0\\
0&0&1\\
1&0&1
\end{bmatrix}
$$
所以
$$
\begin{bmatrix}
0&1&0\\
0&0&1\\
1&0&1
\end{bmatrix}
\times
\begin{bmatrix}
a_{x-3}\\
a_{x-2}\\
a_{x-1}
\end{bmatrix}=
\begin{bmatrix}
a_{x-2}\\
a_{x-1}\\
a_{x}
\end{bmatrix}
$$
那么
$$
\begin{bmatrix}
0&1&0\
0&0&1\
1&0&1
\end{bmatrix}^p
\times
\begin{bmatrix}
a_1=1\
a_2=1\
a_3=1
\end{bmatrix}
\begin{bmatrix}
a_{n-2}\
a_{n-1}\
a_{n}
\end{bmatrix}
$$
中的 $p$ 是多少呢？
考虑举例子。
当 $n=4$ 时，$p=1$ 即可符合要求。
故 $p=n-3$。
$$ \begin{bmatrix} 0&1&0\\ 0&0&1\\ 1&0&1 \end{bmatrix}^{n-3} \times \begin{bmatrix} 1\\ 1\\ 1 \end{bmatrix} = \begin{bmatrix} a_{n-2}\\ a_{n-1}\\ a_{n} \end{bmatrix} $$
对于前一个矩阵可以用矩阵快速幂在 $\log n$ 的时间内求出，再进行依次矩阵乘法即可。
特别的，对应 $n\le3$ 的情况要进行特判，直接输出 $1$。
时间复杂度为 $O(T\times L^3\log n))$，其中 $L=3$。
斐波那契数列
题意简述
斐波那契数列是满足如下性质的一个数列：
$$ F_n = \left\{\begin{aligned} 1 \space (n \le 2) \\ F_{n-1}+F_{n-2} \space (n\ge 3) \end{aligned}\right. $$
请你求出 $F_n \bmod (10^9 + 7)$ 的值 $1\le n<2^{63}$。
算法分析
$n$ 的范围较大，难以递推。由于递推式已知，故可以使用矩阵加速递推。
由于 $F_n$ 仅和 $F_{n-1},F_{n-2}$ 有关，故设计 $f(x-1)=\begin{bmatrix}F_{n-2}\\F_{n-1}\end{bmatrix},f(x)=\begin{bmatrix}F_{n-1}\\F_{n}\end{bmatrix}$
故矩阵 $P$ 为 $2\times2$ 的矩阵，且满足 $P\times f(x-1)=f(x)$。
使用待定系数法，可得
$$
P=
\begin{bmatrix}
0&1\\
1&1
\end{bmatrix}
$$
所以
$$
\begin{bmatrix}
0&1\
1&1
\end{bmatrix}
\times
\begin{bmatrix}
F_{n-2}\
F_{n-1}
\end{bmatrix}
\begin{bmatrix}
F_{n-1}\
F_{n}
\end{bmatrix}
$$
同理快速幂要乘的次数为 $n=2$ 次。
由此可以发现一个规律，设特判的数为 $1\sim i$，那么第 $n\,(n>i)$ 项的快速幂次数为 $n-i$。
时间复杂度为 $O(L^3\log n)$，其中 $L=2$。
广义斐波那契数列
题意简述
广义的斐波那契数列是指形如 $a_n=p\times a_{n-1}+q\times a_{n-2}$ 的数列。
给定数列的两系数 $p$ 和 $q$，以及数列的最前两项 $a_1$ 和 $ a_2$，另给出两个整数 $n$ 和 $m$，试求数列的第 $n$ 项 $a_n$ 对 $m$ 取模后的结果。
算法分析
考虑矩阵加速递推。
$a_n$ 只和 $a_{n-1}$ 和 $a_{n-2}$ 有关，所以设计 $f(x-1)=\begin{bmatrix}a_{x-2}\\a_{x-1}\end{bmatrix},f(x)=\begin{bmatrix}a_{x-1}\\a_{x}\end{bmatrix}$。
可知 $P$ 为 $2\times2$ 的矩阵，且 $P\times f(x-1)=f(x)$。
令 $P=\begin{bmatrix}i&j\\k&l\end{bmatrix}$，那么有
$$
\begin{bmatrix}
i&j\
k&l
\end{bmatrix}
\times
\begin{bmatrix}
a_{x-2}\
a_{x-1}
\end{bmatrix}
\begin{bmatrix}
a_{x-1}\
a_{x}
\end{bmatrix}
$$
则可得
$$
\begin{cases}
i\times a_{x-2}+j\times a_{x-1}=a_{x-1}⇒i=0,j=1\\
k\times a_{x-2}+l\times a_{x-1}=a_x=p\times a_{n-1}+q\times a_{n-2}⇒k=p,l=q
\end{cases}
$$
所以 $P=\begin{bmatrix}0&1\\p&q\end{bmatrix}$。
故
$$
\begin{bmatrix}
0&1\
p&q
\end{bmatrix}^{n-2}
\times
\begin{bmatrix}
a_1\
a_2
\end{bmatrix}
\begin{bmatrix}
a_{n-1}\
a_{n}
\end{bmatrix}
$$
时间复杂度为 $O(L^3\log n)$，其中 $L=2$。
斐波那契公约数
题意简述
对于 $\text{Fibonacci}$ 数列：
$$ f_i = \begin{cases} [i = 1] & i \leq 1 \\ f_{i - 1} + f_{i - 2} & i \gt 1 \end{cases} $$
请求出 $\gcd(f_n, f_m)\bmod10^8$。
算法分析
引理：$\gcd(f_i,f_j)=f_{\gcd(i,j)}$。
证明
晚点写。
那么直接用矩阵快速幂求出 $f_{\gcd(n,m)}$ 即可。
时间复杂度 $O(L^3\log\gcd(n,m))$，其中 $L=2$。