给定长为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的模板题。