一般思路总结，例题汇总思路推演，代码模板。
一般思路
对一个向量进行线性变换从而产生一个新的向量，矩阵就是用来描述这种线性变换的。所谓线性变换，新的向量的每个分量都是原向量的分量的线性组合。所谓线性组合，就是数乘和相加的组合。这都是老生常谈，在此只是不严谨地一提。
矩阵乘法符合结合律，从而对于矩阵幂次特别大的情况，快速幂运算可以像整数快速幂一样运用。这为我们计算一个数列的下标很大的某项提供了可能。
对于两个大小是$n \times n$的方阵，矩阵乘法运算的时间复杂度是$O(n^3)$。从而对于大小是$n\times n$的方阵，计算其$k$次幂的时间复杂度是$O(n^3 \log(k))$。从而这里的$n$一般不大，通常满足$n \le 100$，而$k$可能达到$10^{18}$。对于答案取模也是常规操作，模数$M$一般在$10^9$以内规模，在此规模下用long long乘法不会溢出。
常常要求某数列的第$k$项。解题的关键在于：设所求数列为$f(k)$，则需要试图将$f(k)$展开成若干数列的第$k-1$项的线性组合的形式，而这些数列的第$k$项又可以被相互或用其他数列的第$k-1$项线性地表示，直到每个数列的第$k$项都可被其他数列的第$k-1$项线性表示。线性组合的系数是常数，填入变换矩阵中，并用快速幂升次；再通过初始值确定初始矩阵，乘上即可。
以下是常见题型。本文题单参考[kuangbin]各种各样的题单(去重后) - Virtual Judge。
线性递推
CodeForces - 450B
如Fibonacci数列的扩展形式：
$$
f_0=x,f_1=y,f_{n}=af_{n-1}+bf_{n-2}
$$
这个形式直接就是一个线性组合，$f_{n-2}$需要看作是数列$g_n = f_{n-1}$的第$n-1$项，即：
$$
\begin{pmatrix}
f_n \\
g_n
\end{pmatrix}
=
\begin{pmatrix}
a & b \\
1 & 0
\end{pmatrix}
\begin{pmatrix}
f_{n-1}\\
g_{n-1}
\end{pmatrix}
$$
当然这样写稍嫌麻烦，因为一般不必引入$g$。这样写是为了突显通法。
初始值是：
$$
\begin{pmatrix}
f_1 \\
g_1
\end{pmatrix} =
\begin{pmatrix}
y \\
x
\end{pmatrix}
$$
从而答案是：
$$
\begin{pmatrix}
f_n \\
g_n
\end{pmatrix}
=
\begin{pmatrix}
a & b \\
1 & 0
\end{pmatrix} ^{n-1}
\begin{pmatrix}
y \\
x
\end{pmatrix}
$$
类似的题目还有HDU - 4990（简单讨论奇偶即可），UVA - 10870，UVA - 10689 。另有一些题目需要将类Fibonacci数列和其他知识结合，需要求出数列某项是完成题目的必要不充分条件，如FZU - 1911（巧妙构造）和UVA - 11885（巧妙找规律）。
稍复杂些的线性递推关系
HDU - 5015
通过观察数据范围，可以知道需要按列递推，即需要将第$j$列的元素都用第$j-1$列的元素线性表示。首先有
$$
a_{0,j} = 10 \times a_{0,j-1} + 3
$$
其次观察得到
$$
a_{1,j}=a_{0,j}+a_{1,j-1} = 10 \times a_{0,j-1} + 3 + a_{1,j-1}
$$
$$
a_{2,j}=a_{1,j}+a_{2,j-1} = 10 \times a_{0,j-1} + 3 + a_{1,j-1} + a_{2,j-1}
$$
$$
\dots
$$
$$
a_{i,j}=10 \times a_{0,j-1} + 3 + \sum_{k=1}^i a_{k,j-1}
$$
这样就没问题了，递推矩阵是：
$$
\begin{pmatrix}
a_{0,j} \\
a_{1,j} \\
a_{2,j} \\
\dots \\
a_{i,j} \\
1 \\
\end{pmatrix}
=
\begin{pmatrix}
10 & 0 & 0 & \dots & 0 & 3 \\
10 & 1 & 0 & \dots & 0 & 3 \\
10 & 1 & 1 & \dots & 0 & 3 \\
\dots & \dots & \dots & \dots & \dots & \dots \\
10 & 1 & 1 & \dots & 1 & 3 \\
0 & 0 & 0 & \dots & 0 & 1
\end{pmatrix}
\begin{pmatrix}
a_{0,j-1} \\
a_{1,j-1} \\
a_{2,j-1} \\
\dots \\
a_{i,j-1} \\
1 \\
\end{pmatrix}
$$
注意体会常数$1$（可以视为引入一个常数列）是如何参与到递推运算中的。
初始值是输入给定的，注意应设$a_{0,0}=23$.
UVA - 10655
给定$a+b$和$ab$的值，求$a^n+b^n$。
设$f_n = a^n + b^n$，考虑$f_n$的递推关系。观察到：
$$
( a^{n-1} + b^{n-1} )(a+b) = a^n + b^n + ab(a^{n-2} + b^{n-2})
$$
从而：
$$
f_n = (a+b)f_{n-1} - abf_{n-2}
$$
初始值是
$$
f_0 = 2, f_1 = a+b
$$
这就成了类Fibonacci数列。
HDU - 4565
求
$$
\lceil (a + \sqrt b ) ^n \rceil \mod {m}
$$
其中$(a-1)^2 < b < a^2$。
需要构造共轭式。根据$a,b$的范围关系，观察到当$n>0$时，
$$
\lceil (a + \sqrt b ) ^n \rceil = (a + \sqrt b ) ^n + (a - \sqrt b ) ^n
$$
然后令$x=a+\sqrt b$，$y=a-\sqrt b$，观察到$x+y$和$xy$都是整数，就可以利用上面UVA - 10655的结论解决。
CodeForces - 392C
由数据范围显然对$n$递推。设所求和是$S_n(k)=\sum_{i=1}^n A_i(k)$，则有
$$
S_n(k) = A_n(k) + S_{n-1}(k)
$$
现在考虑将$A_n(k)$的$n$下标向前递推：
$$
\begin{align}
A_n(k) &= F_n \times n^k \\
&= (F_{n-1}+F_{n-2}) \times n^k \\
&=F_{n-1}(n-1+1)^k + F_{n-2}(n-2+2)^k \\
&=\sum_{j=0}^k F_{n-1} {k \choose j} (n-1)^j + \sum_{j=0}^k F_{n-2} {k \choose j}(n-2)^j 2^{k-j} \\
&=\sum_{j=0}^k {k \choose j} A_{n-1}(j) + \sum_{j=0}^k {k \choose j} 2^{k-j} A_{n-2}(j)
\end{align}
$$
虽然形式稍微复杂了些，但$n$的下标确实被化成了$n-1$和$n-2$，只是要记录所有$0 \le j \le k$对应的值。最后递推矩阵的形式稍微复杂了些，此处不写了，但可以观察到里面本身有个帕斯卡三角形，这也方便了我们求组合数。注意矩阵的边长是$2(k+1)+1=2k+3$，多出来的$1$是给$S_n(k)$（或$S_{n-1}(k)$也可）递推用。
HDU - 4686
可以设
$$
f(n) = \sum_{i=1}^{n-1} a_i b_i \\
g(n) = \sum_{i=1}^{n-1} a_i \\
h(n) = \sum_{i=1}^{n-1} b_i \\
k(n) = n-1 \\
c(n) = 1
$$
然后一通代数变形就做出来了。
类似题目还有UVA - 11551。
利用矩阵循环性质加速乘法
UVA - 1386
观察到转移矩阵的每一行都是上一行向右位移一格得到的，即使升次之后也是如此，原因是每个位置都应该是等价的。这样的话，就可以把矩阵乘法的的复杂度优化到$O(n^2)$，因为对乘法的结果只用算一行就行了。用此法就可以过本题$n=500$的数据范围。
矩阵分治
UVA - 11149
计算
$$
\sum_{i=1}^k A^i
$$
注意不能用等比数列求和公式，因为逆元可能不存在。正确的做法是分治。对于偶数$k$，
$$
\sum_{i=1}^k A^i = \left(\sum_{i=1}^{k/2} A^i \right)+ A^{k/2} \left(\sum_{i=1}^{k/2} A^i \right)
$$
对于奇数$k$，只要先算$k-1$时候的函数值，再加上$A^k$即可。
代码模板
1 | ll MOD; |