test/src/polynomial/berlekamp_massey/find_linear_recurrence.test.cpp

• View this file on GitHub
• Last update: 2024-01-30 20:59:32+09:00
• Problem: https://judge.yosupo.jp/problem/find_linear_recurrence

Depends on

• Berlekamp Massey (線形回帰数列の係数計算) (library/polynomial/berlekamp_massey.hpp)

Code

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

#include <iostream>
#include <atcoder/modint>

#include "library/polynomial/berlekamp_massey.hpp"

using mint = atcoder::modint998244353;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::size_t n;
    std::cin >> n;
    std::vector<mint> s(n);
    for (auto &e : s) {
        int v;
        std::cin >> v, e = v;
    }
    std::vector<mint> C = suisen::find_linear_recuurence(s);
    std::cout << C.size() - 1 << '\n';
    for (std::size_t i = 1; i < C.size(); ++i) {
        std::cout << C[i].val();
        if (i + 1 != C.size()) std::cout << ' ';
    }
    std::cout << '\n';

    return 0;
}

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

#include <iostream>
#include <atcoder/modint>

#line 1 "library/polynomial/berlekamp_massey.hpp"



#include <cassert>
#include <vector>

namespace suisen {
    /**
     * @brief Find linear recurrence in O(|s|^2) time
     * @tparam F Arbitrary field (operator +, -, *, /, +=, -=, *=, /= must be defined)
     * @param s Prefix of a linearly reccurent sequence
     * @return The vector of length L+1 c s.t. c_0=1 and s_i=Sum[j=1,L]c_i*s_{i-j} for all i>=L, where L is the minimum integer s.t. there exists such c of length L+1.
     */
    template <typename F>
    std::vector<F> find_linear_recuurence(const std::vector<F>& s) {
        std::vector<F> B{ 1 }, C{ 1 };
        B.reserve(s.size()), C.reserve(s.size());
        F b = 1;
        std::size_t L = 0;
        for (std::size_t N = 0, x = 1; N < s.size(); ++N) {
            F d = s[N];
            for (std::size_t i = 1; i <= L; ++i) d += C[i] * s[N - i];
            if (d == 0) {
                ++x;
            } else {
                F c = d / b;
                if (C.size() < B.size() + x) C.resize(B.size() + x);
                if (2 * L > N) {
                    for (std::size_t i = 0; i < B.size(); ++i) C[x + i] -= c * B[i];
                    ++x;
                } else {
                    std::vector<F> T = C;
                    for (std::size_t i = 0; i < B.size(); ++i) C[x + i] -= c * B[i];
                    L = N + 1 - L, B = std::move(T), b = d, x = 1;
                }
            }
        }
        C.resize(L + 1);
        for (std::size_t N = 1; N <= L; ++N) C[N] = -C[N];
        return C;
    }
} // namespace suisen



#line 7 "test/src/polynomial/berlekamp_massey/find_linear_recurrence.test.cpp"

using mint = atcoder::modint998244353;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::size_t n;
    std::cin >> n;
    std::vector<mint> s(n);
    for (auto &e : s) {
        int v;
        std::cin >> v, e = v;
    }
    std::vector<mint> C = suisen::find_linear_recuurence(s);
    std::cout << C.size() - 1 << '\n';
    for (std::size_t i = 1; i < C.size(); ++i) {
        std::cout << C[i].val();
        if (i + 1 != C.size()) std::cout << ' ';
    }
    std::cout << '\n';

    return 0;
}

Back to top page