【学习笔记】Berlekamp-Massey

前言

好像之前就学过，但是因为洛谷板子要写线性递推所以鸽了。

今天才发现洛谷板子原来不用写多项式取模，那没事了。

$\text{BM}$ 的作用

这个东西十分厉害，可以用来求解数列递推式，一般还可以得到最短的递推式。所以如果有时候的意识到答案是个线性递推式，直接把 $\text{BM}$ 拉过来，可能有奇效（

这个东西的核心思想在于，增量地使得每次加入数列新的一项后，递推式仍然合法。

假设现在给出了一个序列 $\{x_n\}$，表示数列第 $0$ 到 $n-1$ 项分别是多少，那么也就是我们希望求出一个长度为 $m$ 的递推式 $\{c_m\}$，满足对于所有 $p\ge m$，有：

$$ \sum_{i=0}^{p-1} c_i\times x_{p-i-1}-x_p=0 $$

假设现在已经得到了一个递推式，但是在 $p$ 这一项的时候，上式值为 $v\ne 0$，则现在需要修一修递
推式。

注意到当前的递推式，可以使得 $p$ 之前的每一个值 $=0$，唯独 $p$ 这里的值 $\ne 0$。

假设这不是第一次我们发现这个问题了，在 $p'<p$ 的时候也遇到过，当时的值为 $v'$。那我可以直接把当时那个递推式拉过来，乘上 $\dfrac{v}{v'}$，加到当前的递推式上，由于 $p'$ 当时的递推式在 $p'$ 之前也会 $=0$，所以不会改变之前的正确性。

如果是第一次，直接当初值（

至于求最短递推式，直接每次考虑把哪个 $p'$ 拉过来用的时候，选择使得递推式长度最短的拿过来用就行了。

模板

$\text{link}$

这题还要一个线性递推，但是可以直接暴力多项式取模，做到 $\mathcal{O}(k^2\log n)$，其中 $k$ 是递推式长度。

namespace Berlekamp_Massey {
    vec<int> BM(const vec<int> &F) {
        vec<int> cur, pre, nxt; cur.clear(), pre.clear(), nxt.clear();
        int pre_id = 0, pre_val = 0;
        for(int i = 0, val, coe; i < (int)F.size(); ++i) {
            val = mod - F[i];
            for(int j = 0; j < (int)cur.size(); ++j) (val += cur[j] * F[i - j - 1]) %= mod;
            if(!val) continue;
            if(!(int)cur.size()) { cur.resize(i + 1), pre_id = i, pre_val = val; continue; }
            coe = (mod - val) * inv(pre_val) % mod; nxt.clear();
            nxt.resize(i - pre_id - 1); nxt.pb(mod - coe);
            for(auto v : pre) nxt.pb(v * coe % mod);
            if(nxt.size() < cur.size()) nxt.resize(cur.size());
            for(int j = 0; j < (int)cur.size(); ++j) modadd(nxt[j], cur[j]);
            if(i - pre_id + (int)pre.size() >= (int)cur.size()) pre = cur, pre_id = i, pre_val = val;
            cur = nxt;
        } for(auto &x : cur) x = (x + mod) % mod;
        return cur;
    }
}