多校 3 - 1001. 求和

发现不总结会忘记，我就写一下。

发现，从 \(f_i\rightarrow f_j\) 是困难的，但是从 \(f_{[i-k+1,i]}\rightarrow f_{[i-k+2,i+1]}\) 是简单的。

具体的，

\[\begin{bmatrix} f_{i-k+2}\\ f_{i-k+3}\\ \vdots\\ f_{i+1}\end{bmatrix} =\begin{bmatrix} 0&1&0&\cdots&0\\ 0&0&1&\cdots&0\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 0&0&0&\cdots&1\\ a_k&a_{k-1}&a_{k-2}&\cdots& a_1\\\end{bmatrix} \begin{bmatrix} f_{i-k+1}\\ f_{i-k+2}\\ \vdots\\ f_{i}\end{bmatrix} \]

但是直接矩阵乘法是 \(\mathcal{O}(nk^3)\) 的，需要优化。

根据 Hamilton-Cayley 定理：

对于 \(M\) 的特征多项式：\(p(\lambda)=\det(\lambda I-M)=\lambda^k+c_{k-1}\lambda^{k-1}+\cdots +c_0\)，则 \(p(M)=0\)。

即 \(M^n\) 可以表示为 \(I,M,M^2,\cdots , M^{k-1}\) 的线性组合。（\(n\ge k\) 的时候，把 \(n\) 拆成若干个 \(\le k\) 相加）

求 \(M^n\) 的时候，可以分解为 \(M^n=p(M)f(M)+r(M)\)，而 \(p(M)=0\)，则 \(M^n=r(M)\)。\(r(M)\) 是一个次数 \(<k\) 的多项式。那么求出 \(M^n\bmod p(M)\) 即可。

直接暴力求是 \(\mathcal{O}(nk^2)\) 的。可以考虑根号分治，足以通过。

关于求特征多项式：上面的矩阵的 \(0\) 非常多。\(\lambda I-M\) 为：

\[\begin{bmatrix} \lambda&-1&0&\cdots&0&0\\ 0&\lambda&-1&\cdots&0&0\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&0&\cdots&\lambda&-1\\ -a_k&-a_{k-1}&-a_{k-2}&\cdots& -a_2&\lambda-a_1\\ \end{bmatrix} \]

\(k\) 次项一定是 \(\lambda^k\)。如果 \(a_1\) 加入贡献，那么 \(a_2\sim a_k\) 不能贡献，并且会有 \(k-1\) 个 \(\lambda\)，那么就是 \(k-1\) 次项加 \(-a_1\)。同理，容易推出 \(a_2\) 贡献到 \(k-2\) 次项，并且 \(-1\) 和行列式的 \((-1)^{\tau(p)}\) 抵消了，那么也是 \(-a_2\)。以此类推，\(p(\lambda)=\lambda^k-a_1\lambda^{k-1}-a_2\lambda^{k-2}-\cdots -a_{k-1}\lambda-a_k\)。