常系数线性递推
前置知识
多项式除法|取模
该部分见 多项式操作
特征值与特征向量
（这部分我也不怎么理解，就大概记个结论）
对 $n$ 阶矩阵 $A$ 的特征向量 $\vec{v}$ 与，有特征值 $\lambda$ 满足
$$
A\vec v = \lambda\vec v
$$
移项则有 $(\lambda I - A)\vec v = 0$，其中 $I$ 为单位矩阵
那么有解的充要条件是 $det(\lambda I - A) = 0$
令 $f(\lambda) = det(\lambda I - A)$，即此时可将 $det (\lambda I - A)$ 看作一个 $n$ 阶多项式，则称 $f(\lambda)$ 为矩阵 $A$ 的特征多项式，对矩阵 $A$，其任意特征值 $\lambda_0$ 都满足 $f(\lambda_0) = 0$
$\text{Hamiton-Cayley}$定理
对矩阵 $A$ 及其特征多项式 $f(x)$，满足 $f(A) = O$，其中 $O$ 为零矩阵
证明留坑
常系数齐次线性递推
求一个满足 $k$ 阶齐次线性递推数列 $h_i$ 的第 $n$ 项，即
$$
h_n = \sum\limits_{i = 1}^k f_i \times h_{n - i}
$$
它有三个特点
- 常系数：递推系数与下标无关
- 齐次：递推式不存在常数项，就类似 $y = ax + b$ 中 $b = 0$
- 线性：都为一次项
矩阵快速幂
加速矩阵 $A$ $\times$ 初始矩阵 $H$：
$$
\begin{pmatrix}
f_1 & f_2 & f_3 & \cdots & f_n \\
1 & 0 & 0 & \cdots & 0 \\
0 & 1 & 0 & \cdots & 0 \\
\vdots & \vdots & \ddots & \cdots & \vdots \\
0 & 0 & 0 & \cdots & 1
\end{pmatrix}
\times
\begin{pmatrix}
h_k \\
\vdots \\
h_3 \\
h_2 \\
h_1
\end{pmatrix}
=
\begin{pmatrix}
h_{k + 1} \\
\vdots \\
h_4 \\
h_3 \\
h_2
\end{pmatrix}
$$
那么快速幂 $A^nH$ 即可，复杂度 $O (k^3 \log n)$
优化
考虑 $A\vec v = \lambda\vec v$，也就是说现在存在
$$
\begin{pmatrix}
h_{k + 1} \\
\vdots \\
h_4 \\
h_3 \\
h_2
\end{pmatrix}
=
\begin{pmatrix}
\lambda h_k \\
\vdots \\
\lambda h_3 \\
\lambda h_2 \\
\lambda h_1
\end{pmatrix}
$$
推广一下，$h_n = \lambda^{n - 1} h_1$，则
$$
\begin{aligned}
h_{k + 1} &= f_1h_{k -1} + f_2h_{k - 2} + … + f_kh_1 \\
\lambda^kh_1 &= f_1\lambda^{k - 1}h_1 + f_2\lambda^{k - 2}h_2 + … + f_kh_1 \\
\lambda^k &= f_1\lambda^{k - 1} + f_2\lambda^{k - 2} + … + f_k
\end{aligned}
$$
将 $\lambda$ 替换为 $x$，则有 $F(x) = x^k - f_1x^{k - 1} - f_2x^{k - 2} - … - f_k$
此时 $F(x)$ 就是矩阵 $A$ 的特征多项式，有 $F(A) = 0$
考虑等式
$$
x^n = F(x)Q(x) + R(x)
$$
以 $A$ 代入，则有
$$
A^n = R(A)
$$
别忘了现在要求的是 $A^n\vec v$，那么两边同乘 $\vec v$，有 $A^n\vec v = R(A)\vec v$
$R(x)$ 可以通过由 $A(x) = x^n$ 对 $F(x)$ 取模求得，注意此时不能直接取模，因为 $n$ 可以非常大（比如 $n = 1e9）$，无法存下多项式 $x^n$，需要通过快速幂求解
设 $R(x) = \sum\limits_{i = 0}^{k - 1} c_ix^i$，则
$$
A^n\vec v = \sum\limits_{i = 0}^{k - 1}c_iA^i\vec v
$$
而 $A^i\vec v$ 实际上就是
$$
\begin{pmatrix}
h_{k + i} \\
\vdots \\
h_{i + 3} \\
h_{i + 2} \\
h_{i + 1}
\end{pmatrix}
$$
$A$ 的次数最多 $k - 1$，也就是说最多只会取到前 $2k - 1$ 个 $h_i$，我们最后要取得是 $A^n\vec v$ 的第一位，每次乘上一个 $A$ 则令 $h$ 数组向下移一位，那么最终答案即为 $ans = \sum\limits_{i = 0}^{k - 1} c_ih_i$
时间复杂度 $O (k \log k \log n)$
其实每次在求多项式取模的时候都是对 $F(x)$ 取模，所以可以提前对 $F(x)$ 预处理，求出其逆，那么可以少很多常数（虽然我的常数还是贼大就是了。。）
1 |
|
常系数非齐次线性递推
求一个满足 $k$ 阶齐次线性递推数列 $h_i$ 的第 $n$ 项，即
$$
h_n = P(n) + \sum\limits_{i = 1}^k f_i \times h_{n - i}
$$