cp-library-cpp

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub suisen-cp/cp-library-cpp

:heavy_check_mark: test/src/number/stern_brocot_tree/abc273_h.test.cpp

Depends on

Code

#define PROBLEM "https://atcoder.jp/contests/abc273/tasks/abc273_Ex"

#include "library/number/stern_brocot_tree.hpp"

#include <iostream>
#include <map>
#include <set>

#include <atcoder/modint>

using mint = atcoder::modint998244353;

using sbt_node = suisen::sbt_node<int>;
using rational = sbt_node::rational;

mint solve(std::vector<rational> xs) {
    const int n = xs.size();

    const auto all = [](int n) -> mint {
        return (long long) n * (n + 1) / 2;
    };

    mint res = all(n);
    {
        // only (0,1), (1,0)
        auto check = [](rational r) {
            return r == rational{ 1, 0 } or r == rational{ 0, 1 };
        };
        for (int i = 0; i < n; ++i) if (check(xs[i])) {
            xs[i] = { 1, 1 };
            int j = i + 1;
            while (j < n and check(xs[j])) {
                xs[j++] = { 1, 1 };
            }
            // [i, j)
            res -= all(j - i);
            i = j;
        }
    }
    xs.emplace_back(1, 1);
    const auto g = sbt_node::auxiliary_tree(std::vector<sbt_node>(xs.begin(), xs.end()));
    xs.pop_back();

    const int r = g.root();

    std::map<rational, int> mp;
    for (int i = 0; i < n; ++i) mp[xs[i]] = i;

    assert(g.node(r) == sbt_node(1, 1));

    auto dfs = [&](auto dfs, int u, int p) -> std::pair<std::set<int>, mint> {
        std::set<int> su{ -1, n };
        mint nu = 0;

        auto add = [&](int i) {
            if (i == -1 or i == n) return;
            auto it = su.lower_bound(i);
            int r = *it;
            int l = *--it + 1;
            nu += all(r - l);
            su.insert(i);
            nu -= all(r - (i + 1));
            nu -= all(i - l);
        };
        auto merge = [&](std::set<int> &sv, mint nv) {
            if (su.size() < sv.size()) std::swap(su, sv), std::swap(nu, nv);
            for (int i : sv) add(i);
        };

        for (int v : g[u]) if (v != p) {
            int d = sbt_node::dist(g.node(u), g.node(v));
            auto [sv, nv] = dfs(dfs, v, u);
            res += d * nv;
            merge(sv, nv);
        }

        if (auto it = mp.find(g.node(u)); it != mp.end()) add(it->second);
        return { std::move(su), nu };
    };
    dfs(dfs, r, -1);

    return res;
}

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

    int n;
    std::cin >> n;

    mint ans = 0;
    std::vector<rational> xs;

    for (int r = 0; r < n; ++r) {
        int a, b;
        std::cin >> a >> b;
        if (std::gcd(a, b) != 1) {
            ans += solve(xs);
            xs.clear();
            continue;
        }
        xs.emplace_back(a, b);
    }
    ans += solve(xs);
    std::cout << ans.val() << std::endl;
}
#line 1 "test/src/number/stern_brocot_tree/abc273_h.test.cpp"
#define PROBLEM "https://atcoder.jp/contests/abc273/tasks/abc273_Ex"

#line 1 "library/number/stern_brocot_tree.hpp"



#include <algorithm>
#include <cassert>
#include <cstdint>
#include <limits>
#include <type_traits>
#include <utility>
#include <vector>

namespace suisen {
    template <typename Int, std::enable_if_t<std::is_integral_v<Int>, std::nullptr_t> = nullptr>
    struct sbt_node {
        // { a, b } <==> a/b
        using rational = std::pair<Int, Int>;
        using sbt_arc = bool;
        static constexpr sbt_arc Left = false, Right = true;
        using sbt_path = std::vector<std::pair<sbt_arc, Int>>;

        // 1/1
        sbt_node() = default;
        // a/b (a and b must be positive integer)
        sbt_node(Int a, Int b) : sbt_node() {
            assert(a > 0 and b > 0);
            // implicitly computes the continued fraction
            sbt_arc dir = a < b ? Left : Right;
            if (dir == Left) std::swap(a, b);
            for (; b; dir = not dir) {
                const Int q = a / b, r = a % b;
                // If r != 0: [...,1] ----(q   step)----> [...,q+1] = [...,q,1]
                // If r == 0: [...,1] ----(q-1 step)----> [...,q] (end)
                move_down(dir, q - (r == 0));
                a = b, b = r;
            }
        }
        // { a, b } <==> a/b
        sbt_node(const rational& x) : sbt_node(x.first, x.second) {}
        sbt_node(const sbt_path& path) : sbt_node() {
            for (const auto& [dir, first] : path) move_down(dir, first);
        }

        operator rational() const { return { _l.first + _r.first, _l.second + _r.second }; }
        // get the rational number
        rational get() const { return *this; }
        // { inf, sup } of the subtree
        std::pair<rational, rational> range() const { return { _l, _r }; }
        // path from the root node 1/1
        const sbt_path& path() const { return _path; }
        // distance from the root node 1/1
        Int depth() const { return _dep; }

        // lowest common ancestor
        static sbt_node lca(const sbt_node& a, const sbt_node& b) {
            const sbt_path& pa = a.path(), & pb = b.path();
            const int k = std::min(pa.size(), pb.size());
            sbt_node c;
            for (int i = 0; i < k; ++i) {
                if (pa[i] == pb[i]) {
                    c.move_down(pa[i].first, pa[i].second);
                } else {
                    if (pa[i].first == pb[i].first) {
                        // same direction but different lengths
                        c.move_down(pa[i].first, std::min(pa[i].second, pb[i].second));
                    }
                    break;
                }
            }
            return c;
        }
        // lowest common ancestor
        sbt_node lca(const sbt_node& other) { return lca(*this, other); }

        // distance from a to b
        static Int dist(const sbt_node& a, const sbt_node& b) {
            const sbt_node c = lca(a, b);
            return (a.depth() - c.depth()) + (b.depth() - c.depth());
        }
        // distance to another node
        Int dist(const sbt_node& other) { return dist(*this, other); }

        // Check if this is an ancestor of the given node
        bool is_ancestor_of(const sbt_node& a) const { return less(_l, a) and less(a, _r); }
        // Check if this is a descendant of the given node
        bool is_descendant_of(const sbt_node& a) const { return a.is_ancestor_of(*this); }

        // move k steps to the root node. returns true if 0<=k<=depth, false otherwise (and makes no change).
        bool move_up(Int k) {
            if (k < 0 or k > depth()) return false;
            while (k) {
                auto& [dir, first] = _path.back();
                const Int u = std::min(k, first);
                k -= u;
                _dep -= u;
                if (dir == Left) {
                    _r.first -= _l.first * u, _r.second -= _l.second * u;
                } else {
                    _l.first -= _r.first * u, _l.second -= _r.second * u;
                }
                first -= u;
                if (first == 0) _path.pop_back();
            }
            return true;
        }

        // move down k steps to the left
        void move_down_left(Int k) { move(Left, k); }
        // move down k steps to the right
        void move_down_right(Int k) { move(Right, k); }
        // move down k steps in the direction `dir`
        void move_down(sbt_arc dir, Int k) {
            assert(k >= 0);
            if (k == 0) return;
            if (_path.size() and _path.back().first == dir) {
                _path.back().second += k;
            } else {
                _path.emplace_back(dir, k);
            }
            _dep += k;
            if (dir == Left) {
                _r.first += _l.first * k, _r.second += _l.second * k;
            } else {
                _l.first += _r.first * k, _l.second += _r.second * k;
            }
        }

        // move k steps to the destination node. returns true if dist(this, dst)<=k, false otherwise (and makes no change).
        bool move_to(const sbt_node& dst, Int k) {
            const sbt_node a = lca(dst);
            const Int d1 = depth() - a.depth(), d2 = dst.depth() - a.depth();
            if (k <= d1) return move_up(k);
            if (k - d1 > d2) return false;
            *this = dst;
            return move_up(d2 - (k - d1));
        }

        friend bool operator==(const sbt_node& a, const sbt_node& b) { return a._l == b._l and a._r == b._r; }
        friend bool operator!=(const sbt_node& a, const sbt_node& b) { return not (a == b); }
        friend bool operator<(const sbt_node& a, const sbt_node& b) { return less(rational(a), rational(b)); }
        friend bool operator>(const sbt_node& a, const sbt_node& b) { return (b < a); }
        friend bool operator<=(const sbt_node& a, const sbt_node& b) { return not (b < a); }
        friend bool operator>=(const sbt_node& a, const sbt_node& b) { return not (a < b); }

        static int compare_in_order(const sbt_node& a, const sbt_node& b) {
            if (a == b) return 0;
            return a < b ? -1 : +1;
        }
        static int compare_pre_order(const sbt_node& a, const sbt_node& b) {
            if (a == b) return 0;
            if (a.is_ancestor_of(b)) return -1;
            if (b.is_ancestor_of(a)) return +1;
            return a < b ? -1 : +1;
        }
        static int compare_post_order(const sbt_node& a, const sbt_node& b) {
            if (a == b) return 0;
            if (a.is_ancestor_of(b)) return +1;
            if (b.is_ancestor_of(a)) return -1;
            return a < b ? -1 : +1;
        }

        // undirected
        static auto auxiliary_tree(std::vector<sbt_node> xs) {
            std::sort(xs.begin(), xs.end(), [](const sbt_node& a, const sbt_node& b) { return compare_pre_order(a, b) < 0; });
            xs.erase(std::unique(xs.begin(), xs.end()), xs.end());

            const int k = xs.size();

            std::vector<std::vector<int>> g(k);

            std::vector<int> st{ 0 };
            for (int i = 0; i < k - 1; ++i) {
                const sbt_node w = lca(xs[i], xs[i + 1]);

                if (w != xs[i]) {
                    int id_last = st.back();
                    st.pop_back();
                    while (st.size() and w.depth() < xs[st.back()].depth()) {
                        int id_u = st.back();
                        g[id_u].push_back(id_last);
                        g[id_last].push_back(id_u);
                        id_last = id_u;
                        st.pop_back();
                    }
                    int id_w = xs.size();
                    if (st.empty() or xs[st.back()] != w) {
                        st.push_back(id_w);
                        xs.push_back(w);
                        g.emplace_back();
                    } else {
                        id_w = st.back();
                    }
                    g[id_w].push_back(id_last);
                    g[id_last].push_back(id_w);
                }
                st.push_back(i + 1);
            }
            if (k) assert(st.size());
            const int root = st.empty() ? 0 : st.front();
            const int siz = st.size();
            for (int i = 0; i < siz - 1; ++i) {
                g[st[i]].push_back(st[i + 1]);
                g[st[i + 1]].push_back(st[i]);
            }
            struct AuxiliaryTree {
                AuxiliaryTree(int root, const std::vector<sbt_node> &nodes, const std::vector<std::vector<int>> &g) : _root(root), _nodes(nodes), _g(g) {}
                
                int size() const { return _nodes.size(); }

                int root() const { return _root; }
                
                std::vector<int>& operator[](int i) { return _g[i]; }
                const std::vector<int>& operator[](int i) const { return _g[i]; }

                const sbt_node& node(int i) const { return _nodes[i]; }
                const std::vector<sbt_node>& nodes() const { return _nodes; }
            private:
                int _root;
                std::vector<sbt_node> _nodes;
                std::vector<std::vector<int>> _g;
            };
            return AuxiliaryTree{ root, std::move(xs), std::move(g) };
        }
    private:
        rational _l = rational{ 0, 1 }, _r = rational{ 1, 0 };
        Int _dep = 0;
        sbt_path _path{};

        static bool less(const rational& a, const rational& b) {
            using LInt = std::conditional_t<(std::numeric_limits<Int>::digits <= 32), uint64_t, __uint128_t>;
            return LInt(a.first) * b.second < LInt(b.first) * a.second;
        }
    };
}



#line 4 "test/src/number/stern_brocot_tree/abc273_h.test.cpp"

#include <iostream>
#include <map>
#include <set>

#include <atcoder/modint>

using mint = atcoder::modint998244353;

using sbt_node = suisen::sbt_node<int>;
using rational = sbt_node::rational;

mint solve(std::vector<rational> xs) {
    const int n = xs.size();

    const auto all = [](int n) -> mint {
        return (long long) n * (n + 1) / 2;
    };

    mint res = all(n);
    {
        // only (0,1), (1,0)
        auto check = [](rational r) {
            return r == rational{ 1, 0 } or r == rational{ 0, 1 };
        };
        for (int i = 0; i < n; ++i) if (check(xs[i])) {
            xs[i] = { 1, 1 };
            int j = i + 1;
            while (j < n and check(xs[j])) {
                xs[j++] = { 1, 1 };
            }
            // [i, j)
            res -= all(j - i);
            i = j;
        }
    }
    xs.emplace_back(1, 1);
    const auto g = sbt_node::auxiliary_tree(std::vector<sbt_node>(xs.begin(), xs.end()));
    xs.pop_back();

    const int r = g.root();

    std::map<rational, int> mp;
    for (int i = 0; i < n; ++i) mp[xs[i]] = i;

    assert(g.node(r) == sbt_node(1, 1));

    auto dfs = [&](auto dfs, int u, int p) -> std::pair<std::set<int>, mint> {
        std::set<int> su{ -1, n };
        mint nu = 0;

        auto add = [&](int i) {
            if (i == -1 or i == n) return;
            auto it = su.lower_bound(i);
            int r = *it;
            int l = *--it + 1;
            nu += all(r - l);
            su.insert(i);
            nu -= all(r - (i + 1));
            nu -= all(i - l);
        };
        auto merge = [&](std::set<int> &sv, mint nv) {
            if (su.size() < sv.size()) std::swap(su, sv), std::swap(nu, nv);
            for (int i : sv) add(i);
        };

        for (int v : g[u]) if (v != p) {
            int d = sbt_node::dist(g.node(u), g.node(v));
            auto [sv, nv] = dfs(dfs, v, u);
            res += d * nv;
            merge(sv, nv);
        }

        if (auto it = mp.find(g.node(u)); it != mp.end()) add(it->second);
        return { std::move(su), nu };
    };
    dfs(dfs, r, -1);

    return res;
}

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

    int n;
    std::cin >> n;

    mint ans = 0;
    std::vector<rational> xs;

    for (int r = 0; r < n; ++r) {
        int a, b;
        std::cin >> a >> b;
        if (std::gcd(a, b) != 1) {
            ans += solve(xs);
            xs.clear();
            continue;
        }
        xs.emplace_back(a, b);
    }
    ans += solve(xs);
    std::cout << ans.val() << std::endl;
}
Back to top page