常系数齐次线性递推

问题

给定一个线性递推数列 的前 项 ，和其递推式 的各项系数 ，求 。

前置知识

多项式取模。

做法

定义 ，那么答案就是 。

由于 ，所以 ，所以 。

设 。

那么 。

那么就可以通过多次对 加上 的倍数来降低 的次数。

也就是求 。 的次数不超过 ，而 已经给出了，就可以算了。

问题转化成了快速地求 ，只要将

普通快速幂 中的乘法与取模换成

多项式乘法 与

多项式取模 就可以在 的时间复杂度内解决这个问题了。

矩阵的解释

该算法由 Fiduccia 在 1985 年提出，对于 我们定义列向量 为

那么不难发现

而因为 中每一行都满足这个递推关系，我们将 描述为一个线性组合如

有

发现若能将两边的 消去后得到多项式 满足 其中 为一个 的零矩阵。

假设我们要求 可以构造多项式 那么 ，而现在我们可将 写成 而其中零矩阵是没有贡献的，那么 。

但是注意矩阵乘法不满足消去律，此处我们定义矩阵 的特征多项式为 ，其中 为一个 的单位矩阵。Cayley-Hamilton 定理指出 ，我们观察 的形式较为特殊，为下 Hessenberg 矩阵，其特征多项式比起一般矩阵更容易计算。

我们从右下角的 矩阵开始计算特征多项式

右下角 矩阵按照第一行的余子式展开有

观察并归纳有

至此我们可以使用上面的结论。令 有 。而 显然，令 那么

即

我们关注 的第一行就是 已知，那么 可在 时间简单得到。求出 则可用快速幂和多项式取模与上述解释是一样的。该算法常数较大，使用生成函数可以得到一个常数更小的算法，见 一种新的线性递推计算方法。