@Jerusalem
2016-05-14T20:27:26.000000Z
字数 885
阅读 1844
设有递推式,我们需要求。
通常而言,我们是构建一个k阶的矩阵,称A为递推式的伴随矩阵(adjoint matrix);构建一个向量,其中,而就是的值。构建和都是平凡的,这里不再赘述。
那么问题转化为求的值,而主要的瓶颈在于求的值。
设,其中为模的余多项式。容易发现。由Cayley-Hamilton定理,,于是我们只需要关注,也就是说我们只需要求出模。这是简单的快速幂模多项式,使用FFT可以在。
最终我们得到。注意到我们现在仅关心,而对于,都直接表示的值,这也就是递推的初值,于是答案就是。
总时间复杂度为。