求一个满足 \(k\) 阶齐次线性递推数列 \(a_i\) 的第 \(n\) 项，即：
\[f_n=\sum_{i=1}^ka_if_{n-i} \]\(n \leq 10^{18},k\leq 32000\) 。
使用矩阵乘法加速可以做到 \(O(k^3\log n)\) ，运用这一项科技，可以做到 \(O(k\log n)\) 。
数列转化为生成函数
将该线性递推序列看作一个生成函数：
\[F(x)=\sum_{i=0}^{n}f_ix^{i} \]将递推式也视为一个生成函数：
\[A(x)=\sum_{i=0}^ka_ix^i \]显然有：
\[F(x)=F(x)A(x)+R(x) \]其中 \(R(x)\) 为加以修正的常数项。进一步化式子，将其表示为分式形式。
\[F(x)=\frac{R(x)}{1-{A(x)}} \]然后就可以用常系数齐次线性递推来优化了。\(\text{ps.}\) 分母那一坨东西也被叫做数列的特征方程。
常系数齐次线性递推
现在已经将所求数列转化成了一个生成函数的分式形式，所求即为：
\[[x^n]F(x)=\frac{P(x)}{G(x)} \]接下来的一步非常巧妙！将其系数按照奇偶分开：
\[[x^n]F(x)=\frac{P(x)G(-x)}{G(x)G(-x)} \]先看这个分母，将其视为一个整体显然是一个偶函数，因此其奇数项系数为 \(0\) 。将分子系数按照奇偶分开：
\[[x^n]F(x)=\frac{xO(x^2)+E(x^2)}{G(x^2)} \]对 \(n\) 按照奇偶性分类讨论，如果是奇数的话保留左边，否则保留右边不断递归下去，直到 \(n=0\) 也就是仅剩常数项为止。
多项式乘法使用 \(\text{FFT}\) 优化复杂度可以做到 \(O(k \log n \log k)\) 。
标签：系数,frac,log,笔记,齐次,线性,递推 From： https://www.cnblogs.com/oscaryangzj/p/17152289.html