线性递推数列
求第k项
记$n$表示线性递推关系的长度，即每一项都是前$n$项的线性组合。现在要求线性递推数列的第$k$项。
设递推数列为$a_i=\sum_{j=1}^n a_{i-j}c_j$。其特征多项式为$x^n-\sum_{j=1}^n c_jx_{n-j}$。
令$Q(x)=1-\sum_{j=1}^nc_jx^j$，$F(x)$表示线性递推数列的生成函数。则$P(x)=Q(x)F(x)$的度数小于$n$。
由于$P(x)=P(x)\mod x^n$，因此$P(x)=(Q(x)\mod x^n)(F(x)\mod x^n)$。
同理$F(x)=\frac{P(x)}{Q(x)}$。我们实际上要求的则是$[x^k]\frac{P(x)}{Q(x)}$。
\[\begin{aligned} [x^k]\frac{P(x)}{Q(x)}&=[x^k]\frac{P(x)}{Q(x)}\\ &=[x^k]\frac{P(x)Q(-x)}{Q(x)Q(-x)}\\ &=[x^k]\frac{A(x^2)+xB(x^2)}{C(x^2)} \end{aligned}\]如果$k$是奇数，则有：
\[[x^k]\frac{P(x)}{Q(x)}=[x^k]\frac{xB(x^2)}{C(x^2)}=[x^{\frac{k-1}{2}}]\frac{B(x)}{C(x)}\]否则$k$是偶数，则有
\[[x^k]\frac{P(x)}{Q(x)}=[x^k]\frac{A(x^2)}{C(x^2)}=[x^{\frac{k}{2}}]\frac{A(x)}{C(x)}\]上面的过程给出了一个$O(M(n)\log_2k+M(n))$时间复杂度的算法，并且只需要执行$2\log_2k$次的多项式卷积操作。