现在有一个数列aa,并满足以下性质：
an=an−1×xa_ n=a_ n-1 \times x（x为常数）
那么我们可以轻易地写出aa的通项公式：an=xna_ n=x^ n
现在有一个兔子数列：
an=an−1+an−2a_ n=a_ {n-1}+ a_ {n-2}
是否能够找到一种表示方法，使得an=xna_ n=x^ n？

现在我们钦定存在xx满足次递推式。（也就是ana_ n可以被用xnx^ n表示出来）
那么会有xn=xn−1+xn−2x^ n=x^ {n-1}+x^ {n-2}
这时候线性的用处就体现出来了。
x2=x+1x^2=x+1
这时候就有了两个解。
虽然转移一样，可是两个解的x1x^1项与a1a_ 1并不相同。
这里就可以把a1a_ 1看作是k1x1+k2x2k_1x_ 1+k_ 2x_ 2。
根据定义会有：

an=k1x1n+k2x2n=k1(x1n−1+x1n−2)+k2(x2n−1+x2n−2)=an−1+an−2a_ n=k_ 1x_ 1^n+k_ 2x_ 2^n=k_ 1(x_ 1^{n-1}+x_ 1^{n-2})+k_ 2(x_ 2^{n-1}+x_ 2^{n-2})=a_ {n-1}+a_ {n-2}

这样的话，我们就可以去随意构造一个递推的表示了。
也可以把一个符合性质的数列第n项转化成第0项和第1项乘上系数之后的和。
假如说现在的递推式变成了an=∑i=1kcian−ia_ n=\sum_ {i=1}^ {k}c_ ia_ {n-i}，求第nn项呢？
套路一样。
根据定义，an−∑i=1kcian−i=0a_ n-\sum_ {i=1}^ {k}c_ ia_ {n-i}=0
我们可以把ai(i>=k)a_ i(i>=k)不停地往下递归，最后会得到一个k+1k+1项式。
这样只要kk不太大就能解决这个问题了。
中途代入的时候可以用快速幂+FFT

Hamilton-Cayley theorem

对于一个矩阵tt，他有一个特征多项式F()。
但这个特征多项式不一定要带入一个值，它可以代入一个矩阵。
定理：F(t)=0F(t)=0(0矩阵)
不会证明。
一个使用：
定义一个向量vv
会有vF(t)=0vF(t)=0(0向量)
既然都是0了，那多乘几个t也不会影响。
vF(t)tn=0vF(t)t^n=0
用分配律把向量vv展开
会有∑ipivi=0\sum i p_ i v_ i=0
哎好像和某递推式有点像？