特征多项式和常系数线性齐次递推
特征多项式
设 $A$ 为给定的 $n\times n$ 矩阵，$I_n$ 为 $n\times n$ 单位矩阵，$A$ 的特征多项式定义为
$$
p(\lambda )=\det(\lambda I_{n}-A)
$$
其中 $\det$ 表示行列式。
Cayley–Hamilton theorem
根据 凯莱–哈密顿定理，$A$ 满足方程
$$
p(A)=0
$$
其中 $0$ 是零矩阵。
因此我们可以利用这个 $n$ 次的多项式 $p(A)$ 来降低 $A$ 的高次幂。
求特征多项式
代入 $k+1$ 个值，求行列式，插值得到多项式系数。
高斯消元求行列式是 $O(n^3)$，总复杂度 $O(n^4)$。
有 $O(n^3)$ 的做法我就不学了。（点这里）
求矩阵的高次幂
BZOJ 4162: shlw loves matrix II
求 $k\times k$ 的矩阵 $M$ 的 $n$ 次幂。
$k\le 50, n\le 2^{10000}$。
暴力
直接暴力不卡常本机 2s，复杂度$O(k^3\log n)$。
正常做法
先 $O(k^4)$ 求出矩阵的特征多项式 $p(x)$。
然后就要求出 $x^n \bmod p(x)$，直接快速幂，其中乘法和取模都是 $O(k^2)$。
最后暴力乘出 $M^0, M^1, \dotsc, M^{k-1}$，按系数计算答案，复杂度也是 $O(k^4)$。
总复杂度 $O(k^4+k^2\log n)$。
代码在例题里贴。
常系数线性齐次递推
给出系数 $c_1, c_2, \dotsc, c_k$ 和数列 $f$ 的前 $k$ 项 $f_0, f_1, \dotsc, f_{k-1}$。
对于 $n\ge k$ 有 $f_n=\sum\limits_{i=1}^k f_{n-i}c_i$。
求 $f_n$。
暴力
构造出转移矩阵
$$
\begin{bmatrix}
c_1 & c_2 & \cdots & c_{k-1} & c_k \
1 & 0 & \cdots & 0 & 0 \
0 & 1 & \cdots & 0 & 0 \
\vdots & \vdots & \ddots & \vdots & \vdots \
0 & 0 & \cdots & 1 & 0
\end{bmatrix}
\begin{pmatrix}
f_{k-1} \
f_{k-2} \
f_{k-3} \
\vdots \
f_0
\end{pmatrix}
\begin{pmatrix}
f_k \
f_{k-1} \
f_{k-2} \
\vdots \
f_1
\end{pmatrix}
$$
可以做到 $O(k^3\log n)$。
特征多项式优化
上述转移矩阵设为 $A$，特征多项式是
$$
\begin{aligned}
p(\lambda) & =\det(\lambda I-A) \
& = \det\left(
\begin{bmatrix}
\lambda -c_1 & -c_2 & \cdots & -c_{k-1} & -c_k \
-1 & \lambda & \cdots & 0 & 0 \
0 & -1 & \cdots & \lambda & 0 \
\vdots & \vdots & \ddots & \vdots & \vdots \
0 & 0 & \cdots & -1 & \lambda
\end{bmatrix}
\right)
\end{aligned}
$$
对第一行展开
可以发现 $k$ 个代数余子式 $C_{1,1},C_{1,2},\dotsc,C_{1,k}$ 分别是 $\lambda^{k-1}, \lambda^{k-2}, \dotsc, \lambda^0$。
于是 $p(\lambda) = \lambda^k - \sum\limits_{i=1}^k c_i\lambda^{k-i}$。
我们令 $g(x)=x^n \bmod p(x)$，于是 $A^n=\sum\limits_{i=0}^{k-1} g_i A^i$。
令 $\vec{f}=
\begin{pmatrix}
f_{k-1} \
f_{k-2} \
f_{k-3} \
\vdots \
f_0
\end{pmatrix}$，$\left[\vec{a}\right]_ k$ 表示列向量 $\vec{a}$ 的第 $k$ 项。
则
$$
\begin{aligned}
f(n) & =\left[A^n \vec{f}\right]_ k \
& = \left[\sum_{i=0}^{k-1} g_i A^i \vec{f}\right]_ k \
& = \sum_{i=0}^{k-1} g_i \left[A^i \vec{f}\right]_ k \
& = \sum_{i=0}^{k-1} g_i f_i
\end{aligned}
$$
因为 $A\vec{f}$ 相当于转移了一次，转移 $i$ 次后向量的第 $k$ 项即 $f_i$。
实现
其实只需要求 $g(x)=x^n \bmod p(x)$ 就好了。
可以快速幂，暴力取模复杂度 $O(k^2\log n)$，用 NTT 可以优化到 $O(k\log k\log n)$。
例题
shlw loves matrix II
BZOJ 4162: shlw loves matrix II
上面讲过。
代码
1 |
|
【模板】线性递推
模板，需要 NTT。
代码
1 |
|
Shlw loves matrixI
可以暴力取模，由于模数原因也可以用 MTT。
代码
1 |
|
【NOI2017】泳池
咕咕咕。
特征多项式和常系数线性齐次递推