有时候zz出题人喜欢出一些数列找规律计数题(而且验题没试BM)，然后很可能规律就是常系数齐次线性递推。这种题正解往往非常难推，需要一定的数学功底。这时候BM搞搞可能就给水过去了。

Berlekamp-Massey算法

假设我们通过模拟、暴搜等一切合理手段得到了数列的前面一些项。然后要猜出线性递推系数f，使之满足$$a[i]=\sum_{j=1}^{n}{a[i-j]\cdot f[j]}$$

最直接而且理论上有效的方法是直接高斯消元解方程组。如果关系简单，只有两三阶而且系数好算，可能手动解也直接算出来了。但是如果阶数较高，而且情况较复杂，那就很难处理了。因为此时不知道阶数多高，可能算前几项满足到后面又不满足了，还可能弄出无解或任意解的情况。

Berlekamp-Massey算法思路是增量插值。首先它要算出满足前n项的尽可能短的递推式f[pn]。如果发现这个式子到n+1项的时候萎了，相差delta[pn]，那就修改一下：构造另一个递推g，使g递推出来前n项均为0，n+1的时候为当前的差值。那么f和g加一加，就拟合了，弄出一个新的了递推式f[pn+1]。

问题是想要让递推g尽可能短，不然每次长度都+1卵用都没有，所以把与之前有重叠的都用起来。一开始，我们还没弄出递推式，pn=0，说明之前数列都是0，所以前面全部填0即可。
然后考虑pn>0，构造满足上述要求的g。
设fail[pn]=n表示我们之前第pn个搞出来的递推式在算第n项的时候GG了。
设0<=best<pn，再令\(k=\frac{delta[pn]}{delta[fail[best]]}\)。令
$$g=\{0,0,\cdots,k,-k\cdot f[best][1],-k\cdot f[best][2],\cdots\}$$前面的0有i-fail[pn]-1个。
那么用这个g算n之前的项时，它们因为满足递推关系均抵消而为0。而算到n时，我们把它的原来的差值乘上k调整为目标值。即这样的g是满足要求的。
最后，如何让g最短?每次找best时，找令i-fail[best]+len(f[best])最短的即可。注意到算的时候只会用到当前的最新的系数f[pn]和最短的构造用系数f[best]，可以滚动来优化空间。

模质数意义下也一样可以算，需要逆元。

结论：1、不一定有用 ，不是常系数齐次线性递推就凉了 2、打表要打对 3、还是不一定有用，如果出题人水平较高，建议不要和出题人斗智斗勇。

多项式加速高阶线性递推

计算n阶递推的第k项时，矩阵乘法是n^3 log(k)的，不能处理k较大的情况。但是我们也发现计算递推用的矩阵非常特殊，应该有更快的方法。

如果是对角矩阵，或者稍微差一点的Jordan形，幂次非常好算。因此尝试对它特征分解，先求出特征多项式：$$det(A-\lambda E)=(-1)^n(\lambda^n-\lambda^{n-1} f_1 – \lambda^{n-2} f_2 – \cdots – f_n) $$ 发现这个多项式不好解，换个思路，用哈密顿-凯莱定理：$$f为特征多项式，f(\lambda)=0 $$ $$则 f(A)=0$$
于是，把A^k可视为关于A的，次数为k且仅只有一项的多项式。将A^k 对 特征多项式F(A)取模：\(A^k=P(A)\cdot F(A) + R(A)\)，于是只用算余多项式R(A)的系数。
那么如何计算这个k十分大的A^k mod F(A)？对多项式做快速幂即可，只用把取模换成多项式取模。取模可以直接n^2暴力做，也可以用NTT加速到nlogn。

然后就是算矩阵A的前n次方在给定系数下线性组合，直接暴力会达到O(n^4)。注意到我们只关心最终答案，它是R(A)乘上一个递推边界列向量ST的第一项：$$\sum_{i=0}^{n-1}{c_i (A^i \cdot ST)_0}$$
等等，A^i乘上ST后取第一项?那不就是递推的第i项嘛。于是O(n)算就好了啊。

最后列个比较，目标为计算n阶常系数齐次线性递推的第k项：

BM	O(n^2)	要求逆元
暴力递推	O(nk)	有时可以分块打表
矩阵快速幂	O(n^3 log k)
多项式加速递推	O(n^2 logk)	要求逆元
多项式+NTT	O(nlogn logk)	要求模NTT质数