test/yosupo_find_linear_recurrence.test.cpp

View this file on GitHub
Last update: 2026-03-14 20:56:35+09:00
Problem: https://judge.yosupo.jp/problem/find_linear_recurrence

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/find_linear_recurrence"

#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 998244353;
using ll = long long;
using uint = unsigned;
using ull = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;

#include "../util/modint.cpp"
#include "../math/berlekamp_massey.cpp"

int main() {
    int n;
    cin >> n;
    vector<mint> a(n);
    for (int i = 0; i < n; ++i) {
        int x;
        scanf("%d", &x);
        a[i] = x;
    }
    auto c = berlekamp_massey(a);
    printf("%d\n", (int)c.size());
    for (int i = 0; i < (int)c.size(); ++i) {
        if (i) printf(" ");
        printf("%u", c[i].val);
    }
    puts("");
    return 0;
}

#line 1 "test/yosupo_find_linear_recurrence.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/find_linear_recurrence"

#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 998244353;
using ll = long long;
using uint = unsigned;
using ull = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;

#line 1 "util/modint.cpp"



template <uint Mod>
struct modint {
    uint val;
public:
    static modint raw(int v) { modint x; x.val = v; return x; }
    static constexpr uint get_mod() { return Mod; }
    static constexpr uint M() { return Mod; }
    modint() : val(0) {}
    template <class T>
    modint(T v) { ll x = (ll)(v % (ll)(Mod)); if (x < 0) x += Mod; val = uint(x); }
    modint(bool v) { val = ((unsigned int)(v) % Mod); }
    uint &value() noexcept { return val; }
    const uint &value() const noexcept { return val; }
    modint& operator++() { val++; if (val == Mod) val = 0; return *this; }
    modint& operator--() { if (val == 0) val = Mod; val--; return *this; }
    modint operator++(int) { modint result = *this; ++*this; return result; }
    modint operator--(int) { modint result = *this; --*this; return result; }
    modint& operator+=(const modint& b) { val += b.val; if (val >= Mod) val -= Mod; return *this; }
    modint& operator-=(const modint& b) { val -= b.val; if (val >= Mod) val += Mod; return *this; }
    modint& operator*=(const modint& b) { ull z = val; z *= b.val; val = (uint)(z % Mod); return *this; }
    modint& operator/=(const modint& b) { return *this = *this * b.inv(); }
    modint operator+() const { return *this; }
    modint operator-() const { return modint() - *this; }
    modint pow(long long n) const { modint x = *this, r = 1; while (n) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
    modint inv() const { return pow(Mod - 2); }
    friend modint operator+(const modint& a, const modint& b) { return modint(a) += b; }
    friend modint operator-(const modint& a, const modint& b) { return modint(a) -= b; }
    friend modint operator*(const modint& a, const modint& b) { return modint(a) *= b; }
    friend modint operator/(const modint& a, const modint& b) { return modint(a) /= b; }
    friend bool operator==(const modint& a, const modint& b) { return a.val == b.val; }
    friend bool operator!=(const modint& a, const modint& b) { return a.val != b.val; }
};
using mint = modint<MOD>;
#define FIRIEXP_LIBRARY_MINT_ALIAS_DEFINED

/**
 * @brief modint(固定MOD)
 */


#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法
 */
#line 23 "test/yosupo_find_linear_recurrence.test.cpp"

int main() {
    int n;
    cin >> n;
    vector<mint> a(n);
    for (int i = 0; i < n; ++i) {
        int x;
        scanf("%d", &x);
        a[i] = x;
    }
    auto c = berlekamp_massey(a);
    printf("%d\n", (int)c.size());
    for (int i = 0; i < (int)c.size(); ++i) {
        if (i) printf(" ");
        printf("%u", c[i].val);
    }
    puts("");
    return 0;
}