[关闭]
@Jerusalem 2016-05-14T12:27:26.000000Z 字数 885 阅读 1499

常系数线性递推式的快速求单项值方法


前导知识


正文

设有递推式,我们需要求

通常而言,我们是构建一个k阶的矩阵,称A为递推式的伴随矩阵(adjoint matrix);构建一个向量,其中,而就是的值。构建都是平凡的,这里不再赘述。

那么问题转化为求的值,而主要的瓶颈在于求的值。

,其中的余多项式。容易发现。由Cayley-Hamilton定理,,于是我们只需要关注,也就是说我们只需要求出。这是简单的快速幂模多项式,使用FFT可以在

最终我们得到。注意到我们现在仅关心,而对于都直接表示的值,这也就是递推的初值,于是答案就是

总时间复杂度为

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注