Berlekamp-Massey算法模板

Berlekamp-Massey算法模板

#include <cstdio>
#include <vector>
using namespace std;
typedef long long Lint;
const Lint mod = 1e9 + 7;
Lint fpow(Lint a, Lint b) {
    Lint res = 1;
    for (; b; b >>= 1) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
    }
    return res;
}
Lint inv(Lint a) { return fpow(a, mod - 2); }
vector<Lint> BM(const vector<Lint>& a) {
    vector<Lint> last, cur;
    int fail;
    Lint delta;
    for (int i = 0; i < a.size(); i++) {
        Lint t = a[i];
        for (int j = 0; j < cur.size(); j++) t = (t + mod - a[i - j - 1] * cur[j] % mod) % mod;
        if (t == 0) continue;
        if (cur.empty()) {
            cur.resize(i + 1);
            fail = i;
            delta = t;
            continue;
        }
        Lint p = t * inv(delta) % mod;
        vector<Lint> nxt(i - fail - 1);
        nxt.push_back(p);
        for (int j = 0; j < last.size(); j++) nxt.push_back((mod - p) * last[j] % mod);
        if (nxt.size() < cur.size()) nxt.resize(cur.size());
        for (int j = 0; j < cur.size(); j++) nxt[j] = (nxt[j] + cur[j]) % mod;
        if (i - fail + last.size() >= (int)cur.size()) last = cur, fail = i, delta = t;
        cur = nxt;
    }
    return cur;
}

int main() {
    vector<Lint> res = BM(vector<Lint>{1, 1, 2, 3, 5, 8, 13, 21});
    return 0;
}

Berlekamp-Massey算法模板

原文：https://www.cnblogs.com/Bamboo-Wind/p/15032756.html