前置知识
- 矩阵乘法
- (常系数)(齐次)(线性)递推
- 快速幂
- 一点点动态规划知识
简要形式
$$
f_i=C+\sum_{j=1}^{k}a_{j}f_{i-j}
$$
写成矩阵的话是这样的
$$
\begin{pmatrix}
f_{i} & f_{i+1} & \cdots & f_{i+k-1} & C
\end{pmatrix}
\begin{pmatrix}
0 & 0 & \cdots & 0 & a_1 & 0 \\
1 & 0 & \cdots & 0 & a_2 & 0\\
0 & 1 & \cdots & 0 & a_3 & 0\\
\vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\
0 & 0 & \cdots & 1 & a_{k} & 0\\
0 & 0 & \cdots & 0 & 1 & 1
\end{pmatrix}
=
\begin{pmatrix}
f_{i+1} \\
f_{i+2} \\
\vdots \\
f_{i+k} \\
C
\end{pmatrix}
$$
如果$C$是多项式的话，可能还要维护一堆$C$，比如说$j^3,j^2,j$
当然，有时候会遇到一些有若干个变量的线性变换，处理的方式相同
常见套路
- dp模型，但$n$很大，写成矩阵转移后可以进行矩阵快速幂，如求斐波那契数列第$n$项
- 带修改dp模型，在无修改的时候可以写成矩阵转移形式，带修改则只需用线段树维护一下即可，如hdu5068
- 若干个互相独立的点，每个点有变量，每次将连续的一些点的变量进行独立的线性变换，可用某种嵌套数据结构维护，如loj6208
部分应用
斐波那契第$n$项
设$f(0)=0,f(1)=1$，且$\forall i \ge 2, f(i)=f(i-1)+f(i-2)$
即
$$
\begin{pmatrix}
f(i) & f(i+1)
\end{pmatrix}
\begin{pmatrix}
0 & 1 \\
1 & 1
\end{pmatrix}
=
\begin{pmatrix}
f(i+1) & f(i+2)
\end{pmatrix}
$$
所以
$$
\begin{pmatrix}
f(0)) & f(1)
\end{pmatrix}
\begin{pmatrix}
0 & 1 \\
1 & 1
\end{pmatrix}^n
=
\begin{pmatrix}
f(n) & f(n+1)
\end{pmatrix}
$$
算了就这样了……剩下的从习题中看吧……
