本博客部分参考自dtz的博客,Troywar的博客
为什么要来学这个鬼畜的东西呢……因为模拟赛出了一道板题(好吧这实际上就是BZOJ4162):
看到的时候我非常兴奋,这不是一道sb矩阵快速幂题吗?连邻接矩阵都直接给出来了;
结果一看数据范围,算了算$n^3logk=1.25e10$,emmm我咋不知道矩阵快速幂有什么优化方法?
于是我就自闭了,写了50滚粗(然后一个点1008ms一个点1114ms少了20,气傻了)
然后才知道这是个常系数齐次线性递推模板题……
有一个数列递推式为:
$$S_i=\sum\limits_{j=1}^{k}a_jS_{i-j}$$
要求数列第$n$项,矩阵快速幂相信大家都会……但是朴素的矩阵快速幂时间复杂度是$O(k^3logn)$的(听说有些神秘方法可以优化到$O(k^{log_27}n)$但是没啥用),当$k$比较大的时候就GG了,因此需要一些优化。
设$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$
沿用上面的定义,设数列$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