本博客部分参考自dtz的博客，Troywar的博客

前言：

为什么要来学这个鬼畜的东西呢……因为模拟赛出了一道板题（好吧这实际上就是BZOJ4162）：

看到的时候我非常兴奋，这不是一道sb矩阵快速幂题吗？连邻接矩阵都直接给出来了；

结果一看数据范围，算了算$n^3logk=1.25e10$，emmm我咋不知道矩阵快速幂有什么优化方法？

于是我就自闭了，写了50滚粗（然后一个点1008ms一个点1114ms少了20，气傻了）

然后才知道这是个常系数齐次线性递推模板题……

常系数齐次线性递推

0.预备知识：

有一个数列递推式为：

$$S_i=\sum\limits_{j=1}^{k}a_jS_{i-j}$$

要求数列第$n$项，矩阵快速幂相信大家都会……但是朴素的矩阵快速幂时间复杂度是$O(k^3logn)$的（听说有些神秘方法可以优化到$O(k^{log_27}n)$但是没啥用），当$k$比较大的时候就GG了，因此需要一些优化。

1.特征多项式和Cayley-Hamilton定理

设$A$是一个$n$阶矩阵，且数$\lambda$和非零列向量$x$满足

$$Ax=\lambda x (1)$$

则称$\lambda$为矩阵$A$的特征值，$x$为矩阵$A$的特征向量；

稍微变式可以得到

$$(A-\lambda I)x=0$$

其中$I$表示单位矩阵；

此式有非零解当且仅当其行列式

$$|A-\lambda I|=0 (2)$$

(1)式可以看成一个关于$\lambda$的一元$n$次方程，称为矩阵$A$的特征方程，(2)式是关于$\lambda$的$n$次多项式，称为矩阵$A$的特征多项式，记为$\phi(\lambda)$；

注意这里的“特征多项式”指的是广义的多项式，未知数不一定是一个数或字母，也可以是向量或者矩阵；

那么对于任意一个矩阵$A$的特征多项式$\phi(\lambda)$，都有

$$\phi(A)=0（Caylay-Hamilton定理）$$

证明：$\phi(A)=|A-AI|=|0|=0$

2.求解特征多项式

沿用上面的定义，设数列$S$的递推矩阵$A$的特征多项式为$\phi(\lambda)$，则：

$$\phi(\lambda)=|A-\lambda I|=\begin{bmatrix}\lambda&0&\cdots&0&0\\ 0&\lambda&\cdots&0&0\\ \cdots&\cdots&\cdots&\cdots&\cdots\\ 0&0&\cdots&\lambda&0\\ 0&0&\cdots&0&\lambda\end{bmatrix}-\begin{bmatrix}0&0&\cdots&0&a_k\\ 1&0&\cdots&0&a_{k-1}\\ 0&1&\cdots&0&a_{k-2}\\ \cdots&\cdots&\cdots&\cdots&\cdots\\ 0&0&\cdots&1&a_1\end{bmatrix}$$

$$=\begin{bmatrix}\lambda&0&\cdots&0&-a_k\\ -1&\lambda&\cdots&0&-a_{k-1}\\ 0&-1&\cdots&0&-a_{k-2}\\ \cdots&\cdots&\cdots&\cdots&\cdots\\ 0&0&\cdots&-1&\lambda-a_1\end{bmatrix}$$

把$\phi(\lambda)$按最后一列$(j=k)$拉普拉斯展开得

$$\phi(\lambda)=\sum\limits_{i=1}^{k}a_{k-i+1}(-1)^{i+k}\phi(\lambda)_{i,k}$$

其中$\phi(\lambda)_{i,k}$表示$(i,k)$的代数余子式；

化简得：

$$\phi(\lambda)=(-1)^k(\lambda^k-\sum\limits_{i=1}^{k}a_i\lambda^{k-i})$$

常系数齐次线性递推

原文：https://www.cnblogs.com/dcdcbigbig/p/10086518.html