从一个朴素的问题出发：我们需要求出一个序列b[]，使得符合递推式 f(n)=∑i=1..kcif(n−i) f ( n ) = ∑ i = 1.. k c i f ( n − i ) ，且前K项为给出的常数，记为A[]。就比如斐波那契数列，fib[1]=1,fib[2]=1, f(n)=f(n−1)+f(n−2) f ( n ) = f ( n − 1 ) + f ( n − 2 ) 。
真·常系数齐次线性递推是这样子的… 你考虑矩阵乘法优化的做法，就是先搞出一个转移矩阵T，然后把读入的数列前i项做成一个向量v，那么答案就是 vTn−k v T n − k 的最后一位嘛，为了方便，下面n-k写成n。 一个结论是，这个转移矩阵的特征多项式，和上面那个递推式长得差不多，即为 f(x)=xk−∑i=1..kcixk−i f ( x ) = x k − ∑ i = 1.. k c i x k − i ，这个可以把矩阵画出来看看。 根据特征多项式的性质，我们知道f(T)=0，那么 Tn=Tn−H(T)∗f(T) T n = T n − H ( T ) ∗ f ( T ) ，其中H(T)为任意多项式。那么我们就可以得到 Tn=Tn mod f(T) T n = T n m o d f ( T ) ，设右边的表达式为 ∑i=0..k−1xsiTi ∑ i = 0.. k − 1 x s i T i 那么 vTn=∑i=0..k−1xsi∗v∗Ti v T n = ∑ i = 0.. k − 1 x s i ∗ v ∗ T i ，注意到我们只要v*T的最后一项， v∗Ti v ∗ T i 的最后一项，实际上就是递推序列的第 k+i k + i 项，那么我们把递推式的 k+1到2k k + 1 到 2 k 项都做出来，每一项乘上对应的xs[i]然后求和即可。至于多项式取模，暴力即可。 时间复杂度是O(n^2)的，求一项。 以上是如何算特定一项的方法，下面是求通项公式的知识。
形式化地，我们把上面那个递推式移一下项，可以得到 ∑i=0..kf(n−i)ci=0 ∑ i = 0.. k f ( n − i ) c i = 0 ，其中 c0=1,ck≠0 c 0 = 1 , c k ≠ 0 ，如果ck=0就可以把k-1了。 我们把得到的递推关系叫做常系数齐次线性递推，根据k的大小，可叫做k阶…递推。这个式子全都是一次项，所以是线性的，而且右边等于0，那么是齐次的。 非齐次线性递推就是 ∑i=0..kf(n−i)ci=g(n) ∑ i = 0.. k f ( n − i ) c i = g ( n ) ，其中g是关于n的一个多项式，可以看成是一开始那个斐波那契的递推式后面加个多项式，诸如 f(n)=f(n−1)+f(n−2)+n2 f ( n ) = f ( n − 1 ) + f ( n − 2 ) + n 2 。现在先考虑齐次的。
对于原问题，肯定只有一个序列符合递推式。我们如果忽略掉前K项，那实际上是有无限个序列符合递推式的，那么其中有一个是我们要求的答案。
不可能把所有序列找出来再找出正确答案，我们需要一些性质来优化寻找的过程。 性质1：若有两个解（即两个符合条件的数列）a[],b[]，那么a[]+b[]也是一个解。 这个列式子，容易证，宏观地看就是因为线性而齐次。 类比一下01线性基，由上面性质容易知道无限个解的解集里，只有若干个是线性无关的，那么可以把他们当做解集的集，也就是说，其他解都可以通过它们的线性组合得到。 这里线性无关指的是，对于某个解 bx[] b x [ ] ，解集里不存在一个某一项非0的常数序列a[]，使得 ∑ia[i]bi[]=bx[] ∑ i a [ i ] b i [ ] = b x [ ] 。 有个想法，就是把基求出来，我们可以构造任何一个解了。 现在问题是怎么求基。一种可行的方法是用等比数列构造合法的解。 把递推式中的f()替换为x的次幂，我们可以得到一个方程 ∑i=0..kxn−ici=0 ∑ i = 0.. k x n − i c i = 0 ，称之为特征根方程，左边就是特征多项式，记为H(x)。 观察到这个方程在复数域中有k个解（分解因式拆成若干个x-a的乘积）。对于一个解 xi x i ，我们把它叫做特征根， b[n]=xni b [ n ] = x i n 的b就是原递推关系的一个解。 通过一些线性代数的知识可以证明：若每个x都不一样，这k个x对应的b[]是线性无关的。 如果满足这个，那么我们就构造出基了，那么我们再解一个线性方程，求出最终解关于基的线性组合，就成功了。具体地操作就是列出k个方程，第i个是 ∑j=1..kλjbj[i]=A[i] ∑ j = 1.. k λ j b j [ i ] = A [ i ] 。
那如果有相同的解怎么办，即有些x不一样。 设重的根为x1，由于它是根，那么H(x1)=0。 由于他有重，那么H’(x1)=0，即一阶导数在这个点也是0。 证明：设 H(x)=(x−x1)∗Q(x) H ( x ) = ( x − x 1 ) ∗ Q ( x ) ，我们知道Q(x)里面也有一项(x-x1)，那么由 (f(x)g(x))′=f′(x)g(x)+g′(x)f(x) ( f ( x ) g ( x ) ) ′ = f ′ ( x ) g ( x ) + g ′ ( x ) f ( x ) 可得H’(x1)=0。
我们把 ∑i=0..Kcixn−i ∑ i = 0.. K c i x n − i 求个导，又知道在x1处一阶导数为0，得到 ∑i=0..Kci(n−i)x1n−i−1=0 ∑ i = 0.. K c i ( n − i ) x 1 n − i − 1 = 0 ，我们发现， b[n]=nx1n b [ n ] = n x 1 n 也是原递推式的解，（长相差不多）。
上面说的是x1有两个的情况，如果有m个，那么对与H(x)的1~m-1阶导数，我们都可以拉出一个解，第i个解就是 b[n]=ni↓x1n b [ n ] = n i ↓ x 1 n ，由于可以线性组合，我们把下降幂改成次幂即可， b[n]=nix1i b [ n ] = n i x 1 i 。 那么齐次就说完了。
其实也很简单。 也是不考虑前K项。 如果把g(n)变成0，他就是齐次的了，我们可以求出一组基。 然后我们考虑求出非齐次情况下的随便一个解b’[]，那么b’[]+齐次基的线性组合就可以表示任何一组解。 求b’[]我们使用不动点法。 具体地，我们求一个特殊的b’[]，使得它每一项b’[n]为 ∑i≥0aini ∑ i ≥ 0 a i n i 。 由于在把递推式写成f(x)=W(f(x-1))的时候，我们相当于求W(x)=x的不动点，所以这样叫。 由先人经验可知，g(x)是一个m次多项式的时候，b’[n]也是m次多项式，我们就可以设了之后解方程。 就得出b’[]了，然后就成功了。 一个技巧是如果你看出了g(x)是某些熟悉形式的和，那么你可以把熟悉形式的b’[]得出来再求和。
