「算法学习」Berlekamp-Massey 算法

以后可以在考场上找规律力（狂喜）

BM 算法是用来求解一个序列的最短线性递推式的算法，虽然在算法竞赛中没有用它直接出题题目，但是部分题目中的序列元素之间有着线性关系，我们可以借用 BM 找到规律从而更好的解决这类问题。

Description

给定一个序列 $a_1, a_2\cdots,a_n$ ，求这个序列的最短线性递推序列。

我们从前往后考虑这个序列，假设我们现在求出了序列 $a[1\dots i]$ 的递推数列 $r[1\dots m]$ ，考虑如何求出 $a[1\dots i+1]$ 的递推数列。假设 $a_{i + 1}$ 这个元素满足这个递推式，那么显然 $a[1\dots i+1]$ 的最短递推式也是 $r[1\dots m]$ ，否则这个位置就产生了冲突。我们设冲突后的差值 $d = a_{i +1} - a’_{i + 1}$ ，其中 $a’_{i + 1}$ 表示我们用递推式 $r[1\dots m]$ 求出来的错误的 $a_{i + 1}$ ，如果我们可以构造另一个级短的递推式 $t[1\dots m’]$ 满足这个递推式对于 $a[1\dots i]$ 满足求出来的值都是 0，对于 $a_{i + 1}$ 求出来的值是 d，那么新的最短递推式就是 $r + t$ ，那么现在问题就是如何构造 r 了。

我们找到上一个冲突的位置 $p$ ，找到冲突时的递推式 $f[1\dots k]$ ，设这个位置冲突时的差值是 $d’$ ，令 $mul = \frac d {d’}$ ，那么可以构造出 $t = \{0,0,\dots ,mul, -mul \times f\}$ ，（前面有 $i - p - 1$ 个 0），显然这个序列对于任意的 $j < i$ ，递推式得到的结果都是 0，并且当 $j = i$ 时得到的结果是 $d$ （就是拿上一次失配的地方嗯凑凑出来的）。至此，我们就求出了 $a[1\dots i + 1]$ 的最短递推式。

特殊的，我们令空序列的递推式为 $\{0\}$，并且令第一个冲突的位置的递推式也为空。

模拟过程

给定序列 $\{1, 2, 4, 10, 24, 50\}$ ，求他的最短递推式。

开始时序列的递推式为$\{\}$

考虑元素 1，我们用递推式求出的值 $a’ = 0$，发生了冲突，因为1是第一个冲突的位置，所以递推式为 $r = \{0\}$。

考虑元素 2，我们用递推式求出的值 $a’ = 0$，发生了冲突，当前的 $d = 2$，我们找到上一个冲突的位置 1，$d’ = 1$ ，令 $mul = 2$，构造出 $t = \{mul, -mul \times f\}$，即 $\{2, 0\}$，当前的递推式修正为 $r + t$ , 即 $\{2, 0\}$ ，末尾的 0 可以省略，缩写为 $r = \{2\}$

考虑元素 4，满足递推式，跳过。

考虑元素 10，我们求出 $a’ = 8$，再次发生冲突，当前的 $d = 2$ ，我们找到上一个冲突的位置 2， $d’ = 2$ ，令 $mul = 1$，构造出 $t = \{0, mul, -mul \times f \}$ 即 $t = \{0, 1\}$ ，当前的递推式修正为 $r = \{2, 1\}$

考虑元素 24，满足递推式，跳过。

考虑元素 50，我们求出 $a’ = 58$ ，发生冲突，我们令 $mul = -4$ ，构造出 $t = \{0, -4, 8\}$ ，得到递推式 $r = \{2, -3, 8\}$

Code

namespace linear_basis
{

ll tot, fail[maxn], delta[maxn];

vi ps[maxn];

void solve(ll n, ll *x)
{
    ll best = 0;
    rep(i, 1, n)
    {
        ld dt = mod - x[i];
        rep(j, 0, siz(ps[tot]) - 1) red(dt += x[i - j - 1] * ps[tot][j] % mod);
        delta[i] = dt;
        if(dt == 0) continue
        fail[tot] = i;
        if(!tot)
        {
            ps[++ tot].resize(i);
            continue;
        }
        // ld k = -dt / delta[fail[best]];
        ll k = (mod - dt) * power(delta[fail[best]], mod - 2) % mod;
        vi cur;
        cur.resize(i - fail[best] - 1); //trailing 0
        cur.pb(mod - k);
        rep(ll j : ps[best]) cur.pb(j * k % mod);
        if(siz(cur) < siz(ps[tot])) cur.resize(siz(ps[tot]));
        rep(j, 0, siz(ps[tot]) - 1) red(cur[j] += ps[tot][j]);
        if(i - fail[best] + siz(ps[best]) >= siz(ps[tot])) best = tot;
        ps[++ tot] = cur;
    }
    return ps[tot];
}
};

这个板子绝对是对的，因为是从 zzq 那里贴过来的。