Berlekamp-Massey算法

Berlekamp-Massey算法用于在$O(n^2)$的时间内求解数列的递推式。形式化地讲,给定$a_i(i=0,1,2,3…n-1)$,求一组$b_j(j=0,1,2,3…m)$,满足:
$$
\forall i\geq m, a_i=\sum _{j=0}^{m} a_{i-j}b_i
$$
其中或许会有条件限制$m$最小。

构造

考虑现在我们已经有了一个递推式$[f]$且满足了前$k$项