我要是想做线性递推总是要把前 n 个矩阵算出来的吧。

那不就已经 $O(n^4)$ 了吗？

$O(n^3)$ 求特征多项式有什么意义啊 。