特征多项式和常系数线性齐次递推
特征多项式
设 \(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】泳池
咕咕咕。
特征多项式和常系数线性齐次递推