前言 之前我们在矩阵专栏里面讲了线性 DP 优化，可以把$O(n)$的递推转移优化到天才的$O(k^3\log n)$，但是这种只能优化类似于$h_n = 5h_{n-1} + 6h_{n-2}$这种范围不太大的线性递推方程（其构成的整体叫做数列)，而且由于$k$是立方，如果矩阵太大，说不定还不如$O(n)$（$k$在 300 的立方就已经超时了)。所以我们能不能归纳出一个公式呢？直接变成$O(1)$！当然是可以的，这就是我们今天要将的k阶常系数线性递推。 补充说明一下，上面说的$O(1)$只是一种情况…