线性递推数列

Published: January 06, 2022 by Daltao

• Categories:
• algorithm 101

• Tags:

求第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$次的多项式卷积操作。

参考资料

• Golovanov399's comment