常系数齐次线性递推
问题
给定一个线性递推数列
的前
项
,和其递推式
的各项系数
,求
。
前置知识
多项式取模。
做法
定义
,那么答案就是
。
由于
,所以
,所以
。
设
。
那么
。
那么就可以通过多次对
加上
的倍数来降低
的次数。
也就是求
。
的次数不超过
,而
已经给出了,就可以算了。
问题转化成了快速地求
,只要将 普通快速幂 中的乘法与取模换成 多项式乘法 与 多项式取模 就可以在
的时间复杂度内解决这个问题了。
矩阵的解释
该算法由 Fiduccia 在 1985 年提出,对于
我们定义列向量
为

那么不难发现

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

有

发现若能将两边的
消去后得到多项式
满足
其中
为一个
的零矩阵。
假设我们要求
可以构造多项式
那么
,而现在我们可将
写成
而其中零矩阵是没有贡献的,那么
。
但是注意矩阵乘法不满足消去律,此处我们定义矩阵
的特征多项式为
,其中
为一个
的单位矩阵。Cayley–Hamilton 定理指出
,我们观察
的形式较为特殊,为下 Hessenberg 矩阵,其特征多项式比起一般矩阵更容易计算。
我们从右下角的
矩阵开始计算特征多项式

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

观察并归纳有

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

即

我们关注
的第一行就是
已知,那么
可在
时间简单得到。求出
则可用快速幂和多项式取模与上述解释是一样的。该算法常数较大,使用生成函数可以得到一个常数更小的算法,见 一种新的线性递推计算方法。
本页面最近更新:2023/6/27 13:39:08,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:hly1204, Enter-tainer, ksyx, ouuan, QAQAutoMaton, shuzhouliu, thredreams, Tiphereth-A
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用