Berlekamp-Massey法
(math/berlekamp_massey.cpp)

• View this file on GitHub
• Last update: 2026-03-08 22:25:54+09:00

概要

列 s を満たす最小次数の線形漸化式

s_n = c_0 s_{n-1} + c_1 s_{n-2} + ... + c_{L-1} s_{n-L}

の係数列 c を求める。

計算量

$O(N^2)$ (N = s.size())

使い方

vector<T> c = berlekamp_massey(s);

• T は加減乗除と T(0), T(1) が使える体上の型を想定。
• 返り値の長さが最小次数 L。
• 返り値 c[i] は上式の係数 c_i。

Required by

• 線形漸化式(Linear Recurrence) (fps/linear_recurrence.cpp)

Verified with

• test/yosupo_find_linear_recurrence.test.cpp
• test/yosupo_kth_term_of_linearly_recurrent_sequence.test.cpp

Code

template<class T>
vector<T> berlekamp_massey(const vector<T> &s) {
    vector<T> c(1, T(1)), b(1, T(1));
    int l = 0, m = 1;
    T y = T(1);
    for (int n = 0; n < (int)s.size(); ++n) {
        T d = T(0);
        for (int i = 0; i <= l; ++i) d += c[i] * s[n - i];
        if (d == T(0)) {
            ++m;
            continue;
        }
        auto t = c;
        T coef = d / y;
        if ((int)c.size() < (int)b.size() + m) c.resize((int)b.size() + m, T(0));
        for (int i = 0; i < (int)b.size(); ++i) c[i + m] -= coef * b[i];
        if (2 * l <= n) {
            l = n + 1 - l;
            b = t;
            y = d;
            m = 1;
        } else {
            ++m;
        }
    }
    c.erase(c.begin());
    for (auto &x : c) x = -x;
    return c;
}

/**
 * @brief Berlekamp-Massey法
 */

#line 1 "math/berlekamp_massey.cpp"
template<class T>
vector<T> berlekamp_massey(const vector<T> &s) {
    vector<T> c(1, T(1)), b(1, T(1));
    int l = 0, m = 1;
    T y = T(1);
    for (int n = 0; n < (int)s.size(); ++n) {
        T d = T(0);
        for (int i = 0; i <= l; ++i) d += c[i] * s[n - i];
        if (d == T(0)) {
            ++m;
            continue;
        }
        auto t = c;
        T coef = d / y;
        if ((int)c.size() < (int)b.size() + m) c.resize((int)b.size() + m, T(0));
        for (int i = 0; i < (int)b.size(); ++i) c[i + m] -= coef * b[i];
        if (2 * l <= n) {
            l = n + 1 - l;
            b = t;
            y = d;
            m = 1;
        } else {
            ++m;
        }
    }
    c.erase(c.begin());
    for (auto &x : c) x = -x;
    return c;
}

/**
 * @brief Berlekamp-Massey法
 */

Back to top page