library/datastructure/Doubling.hpp

• View this file on GitHub
• Last update: 2025-11-24 18:49:07+09:00
• Include: #include "library/datastructure/Doubling.hpp"

Depends on

• build/pch/stdc++.hpp

Verified with

• test/yukicoder/1097.test.cpp

Code

template <typename Monoid, int LOG> class Doubling {
    using X = typename Monoid::value_type;
    int n;
    bool is_prepared;

    using P = std::pair<int, X>;
    static constexpr P unit = {-1, Monoid::unit()};
    std::vector<std::vector<P>> DP;

    // a から 2^k 動く
    P k_move(const P &a, int k) {
        if (a.first == -1)
            return a;
        const auto [now, val] = a;
        const auto [nxt, cost] = DP[k][now];
        return {nxt, Monoid::op(val, cost)};
    }

    void build() {
        is_prepared = true;
        for (int k = 0; k < LOG - 1; k++)
            for (int v = 0; v < n; v++)
                DP[k + 1][v] = k_move(DP[k][v], k);
    }

  public:
    Doubling() = default;
    Doubling(int n) : n(n), is_prepared(false) {
        DP.assign(LOG, std::vector<P>(n, unit));
    }

    void add_arc(int from, int to, X x) {
        assert(!is_prepared);
        assert(-1 <= to and to < n);
        DP[0][from] = {to, x};
    }

    // [終点,値] 辺が出てない場所から移動する場合は -1 に着く
    P calc(int s, long long step) {
        assert(step <= (1LL << LOG));
        if (!is_prepared)
            build();

        P res{s, Monoid::unit()};
        for (int k = 0; step; k++, step >>= 1)
            if (step & 1)
                res = k_move(res, k);
        return res;
    }
};

#line 1 "library/datastructure/Doubling.hpp"
template <typename Monoid, int LOG> class Doubling {
    using X = typename Monoid::value_type;
    int n;
    bool is_prepared;

    using P = std::pair<int, X>;
    static constexpr P unit = {-1, Monoid::unit()};
    std::vector<std::vector<P>> DP;

    // a から 2^k 動く
    P k_move(const P &a, int k) {
        if (a.first == -1)
            return a;
        const auto [now, val] = a;
        const auto [nxt, cost] = DP[k][now];
        return {nxt, Monoid::op(val, cost)};
    }

    void build() {
        is_prepared = true;
        for (int k = 0; k < LOG - 1; k++)
            for (int v = 0; v < n; v++)
                DP[k + 1][v] = k_move(DP[k][v], k);
    }

  public:
    Doubling() = default;
    Doubling(int n) : n(n), is_prepared(false) {
        DP.assign(LOG, std::vector<P>(n, unit));
    }

    void add_arc(int from, int to, X x) {
        assert(!is_prepared);
        assert(-1 <= to and to < n);
        DP[0][from] = {to, x};
    }

    // [終点,値] 辺が出てない場所から移動する場合は -1 に着く
    P calc(int s, long long step) {
        assert(step <= (1LL << LOG));
        if (!is_prepared)
            build();

        P res{s, Monoid::unit()};
        for (int k = 0; step; k++, step >>= 1)
            if (step & 1)
                res = k_move(res, k);
        return res;
    }
};

Back to top page