前置知识

  • 矩阵乘法
  • (常系数)(齐次)(线性)递推
  • 快速幂
  • 一点点动态规划知识

简要形式

$$
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$

当然,有时候会遇到一些有若干个变量的线性变换,处理的方式相同

常见套路

  1. dp模型,但$n$很大,写成矩阵转移后可以进行矩阵快速幂,如求斐波那契数列第$n$项
  2. 带修改dp模型,在无修改的时候可以写成矩阵转移形式,带修改则只需用线段树维护一下即可,如hdu5068
  3. 若干个互相独立的点,每个点有变量,每次将连续的一些点的变量进行独立的线性变换,可用某种嵌套数据结构维护,如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}
$$

算了就这样了……剩下的从习题中看吧……