常系数齐次线性递推的优化

首先要求$f\times A^n$ $A$为转移矩阵 然后$A^n$直接求的话由于递推的阶数很大不能直接算 设 $$ A^n=P(A)G(A)+R(A) $$ $P,G,R$为关于$A$的多项式 然后把$G$作为矩阵的特征多项式 由$Cayley-Hamilton\ theorem$可知$G(A)=0$ 那么$A^n \equiv R(A)\ mod\ G(A)$ 然后$G(\lambda )=det(\lambda I-A)$可以通过把这个新矩阵的行列式在第一列展开得到（注意这个转移矩阵是第一列从上到下为$a_1\rightarrow a_k$然后初始矩阵(向量)为$f_k\rightarrow f_1$，方程是$f_k=\sum\limits_ia_{k-i}f_i$，那么每乘一次 向量右移一位 第一位变成新的值） $\lambda I-A$就是这个矩阵  $$ G(\lambda)=\sum_{i=0}^{k}a^{k-i}\lambda^i $$ 然后直接多项式取余得到$R$的各项系数 即把$A^n$当作关于$A$的多（单）项式 这样 $A^n$用$A^0$到$A^{k-1}$表示出来了 因为$G=0,A^n=R(A)$ 即 $$ A^n=\sum_{i=0}^{k-1}r_iA^i $$ 那么 $$ ans=\sum_{i=0}^{k-1}r_if_{i} $$