模板题：传送门
【分析】
不难列出转移矩阵：\(\left( \begin{matrix} a_{n} \\ a_{n-1} \\ a_{n-2} \\ \vdots \\ a_{n-k} \end{matrix} \right)= \left( \begin{matrix} f_1 & f_2 & f_3 & \cdots f_k \\ 1 \\ & 1 \\ && \ddots \\ &&& 1 \end{matrix} \right)\cdot \left( \begin{matrix} a_{n-1} \\ a_{n-2} \\ a_{n-3} \\ \vdots \\ a_{n-k-1} \end{matrix} \right)\)
记该转移为 \(\vec A_n=F_k\cdot \vec A_{n-1}\)
不难得出 \(\vec A_n=F_k^n \cdot \vec A_0\)
这里形式化定义了 $a_{-1}, a_{-2}, a_{-3},\cdots $
现在来进行一个求解：
假设我们能找到一个次数尽可能小的多项式函数 \(G\) 使得 \(G(F_k)=0\)
则我们可以得到： \(\vec A_n=F_k^n\cdot \vec A_0=[ Q(F_k)G(F_k)+R(F_k) ]\cdot \vec A_0=R(F_k)\cdot \vec A_0\)
其中，\(R\) 为 \(x^n \bmod G(x)\)
那么，显然有 \(\displaystyle \vec A_n=(\sum_{i=0}^{\text{deg }G-1} r_i\cdot F_k^i)\cdot \vec A_0=\sum_{i=0}^{\text{deg }G-1} r_i\cdot (F_k^i\cdot \vec A_0)=\sum_{i=0}^{\text{deg }G-1}r_i\cdot \vec A_i\)
由于我们最后所求为 \(a_n\) ，仅为 \(\vec A_n\) 的第一个元素；故对等式右边向量 \(\vec A_i\) ，均只需取第一个元素 \(a_i\)
故 \(\displaystyle a_n=\sum_{i=0}^{\text{deg }G-1}r_i\cdot a_i\)
现在我们考虑如何构造 \(G(x)\) 使得 \(G(F_k)=0\)
先给出结论，后续提供证明：
\(\text{deg }G=k+1, g_n=\begin{cases} -f_{k-n}, n<k \\ 1, n=k \end{cases}\)