特征多项式求解常系数线性递推

发布于 2018-05-31  2.94k 次阅读


给定长为m的数列a,求递推数列\(f(n)=\sum _{i=1}^{m}a_{i}f(n-i)\)的第n项,\(n \leq 10^9,m \leq 3000\)。

如果m小一些的话,我们可以用O(m^3logn)的时间复杂度利用矩阵快速幂来解决,但是显然我们需要更优秀的做法。

假设有矩阵A,那么它的特征向量\(x\)和特征值\(\lambda\)定义如下:

$$(A-\lambda E) x=0$$

特征多项式定义如下(就是行列式的值):

$$char(A) = | A - \lambda E |$$

设矩阵\(A\)的特征多项式为\(\phi(A)\),满足\(\phi(A) = 0\)。

那么我们可以这样变形:\(A^n = f(A)g(A)+h(A)\),然后将特征多项式带入g的位置,则\(A^n =h(A)\)。注意到这其实就是进行多项式取模,而h的次数小于等于m,也就是说A^n可以表示成A^i(0<= i <m)的线性组合。

如果这样直接做,复杂度是O(m^4)的,所以我们还需要优化。如果我们有前2m项的值,那么我们就可以凑一凑转移用的列向量,然后可以写出来递推式,之后就可以O(m)算出f(n)的值了。

如果暴力进行多项式取模,那么我们需要算的其实就是x^n这个多项式关于一个低次多项式取模的结果,我们可以从x^1开始倍增,然后在倍增过程中取模,这样的复杂度是\(O(m^2logn)\)的,实测常数比较小,卡卡常的话三四千的数据范围还是比较合理的。

如果用FFT优化的话复杂度就是\(O(mlogmlogn)\)的,但是常数比较大,最多跑到50000以下。但是,如果递推数列没有特殊性质的话,我们在算f的前2m项的时候还是m^2的,需要用多项式取模来优化。

放一份代码,BZOJ的模板题。

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974