给定\(a_0,\cdots,a_{k-1},f_0,\cdots,f_{k-1}\),且\(\forall i\in[k,+\infty),a_i=\sum\limits_{j=1}^kf_ja_{i-j}\),求\(a_n\)。
一眼看上去有点像分治NTT。
设转移矩阵为\(\mathbf A\)。
矩阵快速幂的浪费之处在于我们求出了连续\(k\)项,但是我们实际只关心一项。
假如说我们现在构造出了一组\(c_0,\cdots,c_{k-1}\),使得\(\mathbf A^n=\sum\limits_{i=0}^{k-1}c_i\mathbf A^i\)。
那么答案\((\mathbf f\mathbf A^n)_0=\sum\limits_{i=0}^{k-1}c_i(\mathbf f\mathbf A^i)_0=\sum\limits_{i=0}^{k-1}c_if_i\)。
也就是说如果我们能够构造出一组\(c\),那么我们就能够在\(O(n)\)的时间内求出答案。
接下来考虑如何求出\(c\)。
先把\(\mathbf A^n\)写成这样的形式:\(\mathbf A^n=Q(\mathbf A)G(\mathbf A)+R(\mathbf A)\)。
其中\(R(\mathbf A)=\sum\limits_{i=0}^{k-1}c_i\mathbf A^i\)。
那么可以设\(G(\mathbf A)=\sum\limits_{i=0}^kg_i\mathbf A^i\)。
如果\(G(\mathbf A)=0\)那么就有\(\mathbf A^n\equiv R(\mathbf A)(\mod G(\mathbf A))\)了。
也就是说如果我们能够构造出一组\(g\),那么我们就能够在\(O(k\log k\log n)\)的时间内求出\(c\)。
接下来考虑如何求出\(g\)。
注意到刚才的过程对于任意矩阵都是成立的。
也就是说如果对于任意一个矩阵而言都能轻松找到\(g\)那么矩阵就没用了。
所以\(g\)肯定不是什么好找的东西。然后让我们进入线性代数的内容。
先给出结论:\(\forall i\in[0,k),g_i=-f_{k-1-i},g_k=1\)。
下面将给出推导过程。
先复述几个定义:
对于\(k\)阶方阵\(\mathbf A\),若数\(\lambda\)和\(k\)维非零向量\(\mathbf x\)使得\((\mathbf A-\lambda\mathbf E)\mathbf x=\mathbf0\)成立,则称\(\lambda\)为\(\mathbf A\)的特征值,\(\mathbf x\)为\(\mathbf A\)的特征向量。
上面这个方程有解的充要条件是\(\det(\mathbf A-\lambda\mathbf E)=0\)。
设\(f(\lambda)=\det(\mathbf A-\lambda\mathbf E)\),不难发现这是个关于\(\lambda\)的\(n\)次多项式,而它的\(k\)个解就是\(\mathbf A\)的\(n\)个特征值。
手玩\(\mathbf A\)可以得到\(f(\lambda)=(-1)^k(\lambda^k-\sum\limits_{i=0}^{k-1}a_{k-i-1}\lambda^i)\)。
实际上取个反并不会让\(k\)个解变动,所以我们把它的特征多项式看做\(f(\lambda)=\lambda^k-\sum\limits_{i=0}^{k-1}a_{k-i-1}\lambda^i\)也没问题。
一个矩阵的特征多项式是它的化零多项式。
就是\(f(\mathbf A)=\mathbf0\)。
所以我们就成功求得了\(g\)。
原文:https://www.cnblogs.com/cjoierShiina-Mashiro/p/12109447.html