FFT 优化常系数齐次线性递推式

标签：begin end FFT 矩阵 cdots 齐次 bmatrix 递推 lambda

\(f_i\) 序列满足 \(f_i=\displaystyle\sum_{j=1}^k c_jf_{i-j}\)。\(k\le 32000,n\le 10^9\)。
已知 \(f_1\sim f_k\) 和 \(c_1\sim c_k\)。求 \(f_n\)。

这称为 "\(k\) 次齐次常系数线性递推式"。

---

如果 \(k\) 比较小，可以用矩阵快速幂；但 \(k\) 太大，一次矩阵乘法都很慢。我们可以用 FFT 优化它。复杂度 \(O(k\log k\log n)\)。

先回忆一下矩阵快速幂。

\[\begin{bmatrix}f_n\\f_{n-1}\\\dots\\f_{n-k+1}\end{bmatrix}=\begin{bmatrix}c_1&c_2&\cdots&c_k\\1&0&\cdots&0\\ 0&1&\cdots&0\\\cdots&\cdots&\cdots&\cdots\\\cdots&\cdots&1&0\end{bmatrix}\cdot \begin{bmatrix}f_{n-1}\\f_{n-2}\\\dots\\f_{n-k}\end{bmatrix}\]

记中间的转移矩阵为 \(M\)。定义它的特征多项式 \(\phi(\lambda)=\lambda^k-c_1\lambda^{k-1}-c_2\lambda^{k-2}-\cdots-c_k\)。

标签：begin,end,FFT,矩阵,cdots,齐次,bmatrix,递推,lambda
From： https://www.cnblogs.com/FLY-lai/p/18188252