概述

给定递推方程$\displaystyle f_n=\sum_{i=1}^ka_if_{n-i}$与$f_0,f_1,\dots,f_{k-1}$,求$f_n$

考虑一个小学生算的过程,举个栗子:$\displaystyle f_n=f_{n-1}+f_{n-2}$

则 $$ \begin{aligned} f_5&=\color{red}{f_4+f_3}\\ &=\color{yellow}{2f_3+f_2} \\&=\color{green}{3f_2+2f_1} \\&=\color{blue}{5f_1+3f_0} \end{aligned} $$ 已知这个递推方程的 特征多项式

$\lambda(f)$为$x^2-x-1$,发现这样累积的过程可以类比为 $$ \begin{aligned} x^5&=x^3(x^2-x-1)+\color{red}{x^4+x^3} \\&=x^3(x^2-x-1)+x^2(x^2-x-1)+\color{yellow}{2x^3+x^2} \\&=x^3(x^2-x-1)+x^2(x^2-x-1)+2x(x^2-x-1)+\color{green}{3x^2+2x} \\&=x^3(x^2-x-1)+x^2(x^2-x-1)+2x(x^2-x-1)+3(x^2-x-1)+\color{blue}{5x+3} \end{aligned} $$ 其实是多项式取模的过程

可以证明设$g\equiv x^n\pmod{\lambda(f)}$,则$f_n=\sum\limits_{i=0}^{k-1}g_if_i$

其中$\lambda(f)=x^k-\sum\limits_{i=0}^{k-1}a_ix^i$