Berlekamp–Massey 算法 小记
神秘算法，模拟赛对着死磕了3.5h 然后发现是高科技，大家都不会，但是大家都会 T3 ，输麻了。
这个算法是一个增量构造的过程，我们尝试维护前 \(i-1\) 项的递推式，然后对于加入 第 \(i\) 项后调整。
具体的，假设我们有一个数列 \(1,2,4,10,24,50\)，最初我们的递推式是 \(\{\}\)。
刚开始来了一个 \(1\)，不能干什么，于是随便写个 \(0\) ，递推式变成 \(\{0\}\)。
然后来了一个 \(2\)，这个递推式不适用了。但是上次寄掉的时候显示 \(a_1=1\)，于是我们将递推式加上 \(\{2\}\)，这样递推式变成 \(\{2\}\)。
然后来了一个 \(4\) ，表现良好。
来了一个 \(10\) 就又寄了。上次寄的时候告诉我们 \(a_2=2\)，于是我们可以将递推式加上 \(\{0,1,0\}\)，于是变成 \(\{2,1,0\}\)。
来了一个 \(24\) ，表现良好。
来了一个 \(50\) 就又寄了。上次寄的时候告诉我们 \(a_4-2a_3=2\)，因此我们可以将递推式加上 \(\{0,-4,-8\}\)，于是变成 \(\{2,-3,8\}\)。
那么你就有问题了，这样直接加的话对 \(24\) 的计算没有影响吗？
你手算一下其实是没有关系的，因为这个递推式的系数在第四项才寄掉，而在第三项的时候加和应该是等于 \(0\) 的，因此将第五项加上这个系数时若干个第三项会抵消。
因此我们大致有一个思路了，就是每次找到上一个寄掉的递推式拿来调整，这样调整对前面的递推过程没有影响。
那么这样为啥最短呢？我不知道，但是能过~
一般在题目中用的话不会硬要你最短，你完全可以暴力跑多一点然后计算一个较短的递推式，再用线性递推那一套做到平方 log 就好了。
放一下模板题的 submission