線形漸化式の発見・第 $N$ 項推定
(formal_power_series/linear_recurrence.hpp)

• View this file on GitHub
• Last update: 2022-01-08 20:23:44+09:00
• Include: #include "formal_power_series/linear_recurrence.hpp"
• Link: http://misawa.github.io/others/fast_kitamasa_method.html
• Link: http://sugarknri.hatenablog.com/entry/2017/11/18/233936
• Link: https://atcoder.jp/contests/abc198/submissions/21837815
• Link: https://en.wikipedia.org/wiki/Berlekamp%E2%80%93Massey_algorithm

線形漸化式

漸化式（最小多項式）の推定

Berlekamp-Massey algorithm を用いて，最初の数項から漸化式を推定する．時間計算量は入力数列長 $L$ に対して $O(L^2)$．

vector<mint> a = {1, 1, 2, 3, 5, 8, 11};
auto [d, Crev] = find_linear_recurrence(a);  // (2, [1, -1, -1])

推測して得られた $C^\mathrm{rev}$ は，

$\displaystyle \sum_{j=0}^d C_{i - j}^\mathrm{rev} a_{j} = 0 $

が成立．

$K$ 次線形漸化式に従う数列の第 $N$ 項の，先頭 $K$ 項の寄与への分解

時間計算量は現在の実装だと $O(K^2 \log N)$ （正しくアルゴリズムを設計すれば $O(K \log K \log N)$）．

long long n = 12345678910111213LL;
vector<mint> b = monomial_mod_polynomial(n, Crev);

母関数の言葉で述べると，単項式 $x^n$ を $K$ 次多項式 $C^\mathrm{rev} (x)$ で割った剰余を求めている．先頭 $K$ 項を $[a_0, \dots, a_{K-1}]$ とすると，第$N$ 項の値は $\displaystyle \sum_{i=0}^{K-1} a_i b_i$ で与えられる．

線形漸化式に従う数列の先頭の $L$ 項からの，第 $N$ 項の値の推定

上記を一括で行う．時間計算量は入力数列長 $L$ に対して $O(L^2 \log N)$．

mint kth_term = guess_kth_term(vector<mint>{1, 1, 2, 3, 5, 8}, 12345678910111213);

Required by

• Black box linear algebra を利用した各種高速計算 (linear_algebra_matrix/blackbox_algorithm.hpp)

Verified with

• formal_power_series/test/kitamasa.test.cpp
• formal_power_series/test/linear_recurrence.test.cpp
• linear_algebra_matrix/test/blackbox_matrix_stress.test.cpp
• linear_algebra_matrix/test/det_of_blackbox_matrix.test.cpp

Code

#pragma once
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>

// CUT begin
// Berlekamp–Massey algorithm
// https://en.wikipedia.org/wiki/Berlekamp%E2%80%93Massey_algorithm
// Complexity: O(N^2)
// input: S = sequence from field K
// return: L          = degree of minimal polynomial,
//         C_reversed = monic min. polynomial (size = L + 1, reversed order, C_reversed[0] = 1))
// Formula: convolve(S, C_reversed)[i] = 0 for i >= L
// Example:
// - [1, 2, 4, 8, 16]   -> (1, [1, -2])
// - [1, 1, 2, 3, 5, 8] -> (2, [1, -1, -1])
// - [0, 0, 0, 0, 1]    -> (5, [1, 0, 0, 0, 0, 998244352]) (mod 998244353)
// - []                 -> (0, [1])
// - [0, 0, 0]          -> (0, [1])
// - [-2]               -> (1, [1, 2])
template <typename Tfield>
std::pair<int, std::vector<Tfield>> find_linear_recurrence(const std::vector<Tfield> &S) {
    int N = S.size();
    using poly = std::vector<Tfield>;
    poly C_reversed{1}, B{1};
    int L = 0, m = 1;
    Tfield b = 1;

    // adjust: C(x) <- C(x) - (d / b) x^m B(x)
    auto adjust = [](poly C, const poly &B, Tfield d, Tfield b, int m) -> poly {
        C.resize(std::max(C.size(), B.size() + m));
        Tfield a = d / b;
        for (unsigned i = 0; i < B.size(); i++) C[i + m] -= a * B[i];
        return C;
    };

    for (int n = 0; n < N; n++) {
        Tfield d = S[n];
        for (int i = 1; i <= L; i++) d += C_reversed[i] * S[n - i];

        if (d == 0)
            m++;
        else if (2 * L <= n) {
            poly T = C_reversed;
            C_reversed = adjust(C_reversed, B, d, b, m);
            L = n + 1 - L;
            B = T;
            b = d;
            m = 1;
        } else
            C_reversed = adjust(C_reversed, B, d, b, m++);
    }
    return std::make_pair(L, C_reversed);
}

// Calculate $x^N \bmod f(x)$
// Known as `Kitamasa method`
// Input: f_reversed: monic, reversed (f_reversed[0] = 1)
// Complexity: $O(K^2 \log N)$ ($K$: deg. of $f$)
// Example: (4, [1, -1, -1]) -> [2, 3]
//          ( x^4 = (x^2 + x + 2)(x^2 - x - 1) + 3x + 2 )
// Reference: http://misawa.github.io/others/fast_kitamasa_method.html
//            http://sugarknri.hatenablog.com/entry/2017/11/18/233936
template <typename Tfield>
std::vector<Tfield> monomial_mod_polynomial(long long N, const std::vector<Tfield> &f_reversed) {
    assert(!f_reversed.empty() and f_reversed[0] == 1);
    int K = f_reversed.size() - 1;
    if (!K) return {};
    int D = 64 - __builtin_clzll(N);
    std::vector<Tfield> ret(K, 0);
    ret[0] = 1;
    auto self_conv = [](std::vector<Tfield> x) -> std::vector<Tfield> {
        int d = x.size();
        std::vector<Tfield> ret(d * 2 - 1);
        for (int i = 0; i < d; i++) {
            ret[i * 2] += x[i] * x[i];
            for (int j = 0; j < i; j++) ret[i + j] += x[i] * x[j] * 2;
        }
        return ret;
    };
    for (int d = D; d--;) {
        ret = self_conv(ret);
        for (int i = 2 * K - 2; i >= K; i--) {
            for (int j = 1; j <= K; j++) ret[i - j] -= ret[i] * f_reversed[j];
        }
        ret.resize(K);
        if ((N >> d) & 1) {
            std::vector<Tfield> c(K);
            c[0] = -ret[K - 1] * f_reversed[K];
            for (int i = 1; i < K; i++) { c[i] = ret[i - 1] - ret[K - 1] * f_reversed[K - i]; }
            ret = c;
        }
    }
    return ret;
}

// Guess k-th element of the sequence, assuming linear recurrence
// initial_elements: 0-ORIGIN
// Verify: abc198f https://atcoder.jp/contests/abc198/submissions/21837815
template <typename Tfield>
Tfield guess_kth_term(const std::vector<Tfield> &initial_elements, long long k) {
    assert(k >= 0);
    if (k < static_cast<long long>(initial_elements.size())) return initial_elements[k];
    const auto f = find_linear_recurrence<Tfield>(initial_elements).second;
    const auto g = monomial_mod_polynomial<Tfield>(k, f);
    Tfield ret = 0;
    for (unsigned i = 0; i < g.size(); i++) ret += g[i] * initial_elements[i];
    return ret;
}

#line 2 "formal_power_series/linear_recurrence.hpp"
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>

// CUT begin
// Berlekamp–Massey algorithm
// https://en.wikipedia.org/wiki/Berlekamp%E2%80%93Massey_algorithm
// Complexity: O(N^2)
// input: S = sequence from field K
// return: L          = degree of minimal polynomial,
//         C_reversed = monic min. polynomial (size = L + 1, reversed order, C_reversed[0] = 1))
// Formula: convolve(S, C_reversed)[i] = 0 for i >= L
// Example:
// - [1, 2, 4, 8, 16]   -> (1, [1, -2])
// - [1, 1, 2, 3, 5, 8] -> (2, [1, -1, -1])
// - [0, 0, 0, 0, 1]    -> (5, [1, 0, 0, 0, 0, 998244352]) (mod 998244353)
// - []                 -> (0, [1])
// - [0, 0, 0]          -> (0, [1])
// - [-2]               -> (1, [1, 2])
template <typename Tfield>
std::pair<int, std::vector<Tfield>> find_linear_recurrence(const std::vector<Tfield> &S) {
    int N = S.size();
    using poly = std::vector<Tfield>;
    poly C_reversed{1}, B{1};
    int L = 0, m = 1;
    Tfield b = 1;

    // adjust: C(x) <- C(x) - (d / b) x^m B(x)
    auto adjust = [](poly C, const poly &B, Tfield d, Tfield b, int m) -> poly {
        C.resize(std::max(C.size(), B.size() + m));
        Tfield a = d / b;
        for (unsigned i = 0; i < B.size(); i++) C[i + m] -= a * B[i];
        return C;
    };

    for (int n = 0; n < N; n++) {
        Tfield d = S[n];
        for (int i = 1; i <= L; i++) d += C_reversed[i] * S[n - i];

        if (d == 0)
            m++;
        else if (2 * L <= n) {
            poly T = C_reversed;
            C_reversed = adjust(C_reversed, B, d, b, m);
            L = n + 1 - L;
            B = T;
            b = d;
            m = 1;
        } else
            C_reversed = adjust(C_reversed, B, d, b, m++);
    }
    return std::make_pair(L, C_reversed);
}

// Calculate $x^N \bmod f(x)$
// Known as `Kitamasa method`
// Input: f_reversed: monic, reversed (f_reversed[0] = 1)
// Complexity: $O(K^2 \log N)$ ($K$: deg. of $f$)
// Example: (4, [1, -1, -1]) -> [2, 3]
//          ( x^4 = (x^2 + x + 2)(x^2 - x - 1) + 3x + 2 )
// Reference: http://misawa.github.io/others/fast_kitamasa_method.html
//            http://sugarknri.hatenablog.com/entry/2017/11/18/233936
template <typename Tfield>
std::vector<Tfield> monomial_mod_polynomial(long long N, const std::vector<Tfield> &f_reversed) {
    assert(!f_reversed.empty() and f_reversed[0] == 1);
    int K = f_reversed.size() - 1;
    if (!K) return {};
    int D = 64 - __builtin_clzll(N);
    std::vector<Tfield> ret(K, 0);
    ret[0] = 1;
    auto self_conv = [](std::vector<Tfield> x) -> std::vector<Tfield> {
        int d = x.size();
        std::vector<Tfield> ret(d * 2 - 1);
        for (int i = 0; i < d; i++) {
            ret[i * 2] += x[i] * x[i];
            for (int j = 0; j < i; j++) ret[i + j] += x[i] * x[j] * 2;
        }
        return ret;
    };
    for (int d = D; d--;) {
        ret = self_conv(ret);
        for (int i = 2 * K - 2; i >= K; i--) {
            for (int j = 1; j <= K; j++) ret[i - j] -= ret[i] * f_reversed[j];
        }
        ret.resize(K);
        if ((N >> d) & 1) {
            std::vector<Tfield> c(K);
            c[0] = -ret[K - 1] * f_reversed[K];
            for (int i = 1; i < K; i++) { c[i] = ret[i - 1] - ret[K - 1] * f_reversed[K - i]; }
            ret = c;
        }
    }
    return ret;
}

// Guess k-th element of the sequence, assuming linear recurrence
// initial_elements: 0-ORIGIN
// Verify: abc198f https://atcoder.jp/contests/abc198/submissions/21837815
template <typename Tfield>
Tfield guess_kth_term(const std::vector<Tfield> &initial_elements, long long k) {
    assert(k >= 0);
    if (k < static_cast<long long>(initial_elements.size())) return initial_elements[k];
    const auto f = find_linear_recurrence<Tfield>(initial_elements).second;
    const auto g = monomial_mod_polynomial<Tfield>(k, f);
    Tfield ret = 0;
    for (unsigned i = 0; i < g.size(); i++) ret += g[i] * initial_elements[i];
    return ret;
}

Back to top page