#921609 (C++17(gcc12)) No.2512 Mountain Sequences

提出ソース

結果

問題	No.2512 Mountain Sequences
ユーザー	suisen
提出日時	2023-10-21 01:13:12
言語	C++17(gcc12) (gcc 12.3.0 + boost 1.87.0)
結果	AC
実行時間	1,572 ms / 3,000 ms
コード長	9,850 bytes
コンパイル時間	1,463 ms
コンパイル使用メモリ	113,480 KB
実行使用メモリ	16,640 KB
最終ジャッジ日時	2024-09-21 02:03:37
合計ジャッジ時間	24,566 ms
ジャッジサーバーID （参考情報）	judge4 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	8 ms 5,248 KB
testcase_01	AC	8 ms 5,376 KB
testcase_02	AC	8 ms 5,376 KB
testcase_03	AC	8 ms 5,376 KB
testcase_04	AC	8 ms 5,376 KB
testcase_05	AC	8 ms 5,376 KB
testcase_06	AC	8 ms 5,376 KB
testcase_07	AC	8 ms 5,376 KB
testcase_08	AC	8 ms 5,376 KB
testcase_09	AC	8 ms 5,376 KB
testcase_10	AC	1,567 ms 16,512 KB
testcase_11	AC	1,571 ms 16,512 KB
testcase_12	AC	1,570 ms 16,384 KB
testcase_13	AC	1,571 ms 16,512 KB
testcase_14	AC	1,572 ms 16,512 KB
testcase_15	AC	1,570 ms 16,512 KB
testcase_16	AC	1,567 ms 16,384 KB
testcase_17	AC	1,566 ms 16,512 KB
testcase_18	AC	1,564 ms 16,512 KB
testcase_19	AC	1,564 ms 16,512 KB
testcase_20	AC	793 ms 16,640 KB
testcase_21	AC	798 ms 16,384 KB
testcase_22	AC	796 ms 16,512 KB
testcase_23	AC	798 ms 16,512 KB
testcase_24	AC	793 ms 16,384 KB
testcase_25	AC	95 ms 16,512 KB
testcase_26	AC	98 ms 16,512 KB
testcase_27	AC	97 ms 16,512 KB
testcase_28	AC	106 ms 11,520 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

main.cpp: In function 'std::vector<mint> suisen::binom_sum(const std::vector<std::tuple<int, int, int> >&, const Mint&)':
main.cpp:258:24: warning: structured binding refers to incomplete class type 'const std::tuple<int, int, int>'
  258 |             const auto [a, b, m] = qs[i];
      |                        ^~~~~~~~~

ソースコード

raw source code

#include <algorithm>
#include <cmath>
#include <numeric>
#include <vector>

namespace suisen {
    struct Mo {
        Mo() = default;
        Mo(const int n, const std::vector<std::pair<int, int>> &queries) : n(n), q(queries.size()), b(bucket_size(n, q)), qs(queries), ord(q) {
            std::iota(ord.begin(), ord.end(), 0);
            std::sort(
                ord.begin(), ord.end(),
                [&, this](int i, int j) {
                    const auto &[li, ri] = qs[i];
                    const auto &[lj, rj] = qs[j];
                    const int bi = li / b, bj = lj / b;
                    if (bi != bj) return bi < bj;
                    if (ri != rj) return bi & 1 ? ri > rj : ri < rj;
                    return li < lj;
                }
            );
        }

        // getter methods used in updating functions: AddL, DelL, etc.
        auto get_left()  const { return l; }
        auto get_right() const { return r; }
        auto get_range() const { return std::make_pair(l, r); }
        auto get_query_id() const { return query_id; }

        /**
         * [Parameters]
         * Eval : () -> T : return the current answer
         * AddL : int -> any (discarded) : add    `l` to   the current range [l + 1, r)
         * DelL : int -> any (discarded) : delete `l` from the current range [l, r)
         * AddR : int -> any (discarded) : add    `r` to   the current range [l, r)
         * DelR : int -> any (discarded) : delete `r` from the current range [l, r + 1)
         * 
         * [Note]
         * starting from the range [0, 0).
         */
        template <typename Eval, typename AddL, typename DelL, typename AddR, typename DelR>
        auto solve(Eval eval, AddL add_l, DelL del_l, AddR add_r, DelR del_r) {
            l = 0, r = 0;
            std::vector<decltype(eval())> res(q);
            for (int qi : ord) {
                const auto &[nl, nr] = qs[query_id = qi];
                while (r < nr) add_r(r), ++r;
                while (l > nl) --l, add_l(l);
                while (r > nr) --r, del_r(r);
                while (l < nl) del_l(l), ++l;
                res[qi] = eval();
            }
            return res;
        }
    
        /**
         * [Parameters]
         * Eval : () -> T : return the current answer
         * Add : int -> any (discarded) : add    `i` to   the current range [i + 1, r) or [l, i)
         * Del : int -> any (discarded) : delete `i` from the current range [i, r) or [l, i + 1)
         * 
         * [Note]
         * starting from the range [0, 0).
         */
        template <typename Eval, typename Add, typename Del>
        auto solve(Eval eval, Add add, Del del) {
            return solve(eval, add, del, add, del);
        }

    private:
        int n, q, b;
        int query_id = -1;
        std::vector<std::pair<int, int>> qs;
        std::vector<int> ord;
        int l = 0, r = 0;

        static int bucket_size(int n, int q) {
            return std::max(1, int(::sqrt(3) * n / ::sqrt(std::max(1, 2 * q))));
        }
    };
} // namespace suisen

namespace suisen {
    template <int base_as_int, typename mint>
    struct static_pow_mods {
        static_pow_mods() = default;
        static_pow_mods(int n) { ensure(n); }
        const mint& operator[](int i) const {
            ensure(i);
            return pows[i];
        }
        static void ensure(int n) {
            int sz = pows.size();
            if (sz > n) return;
            pows.resize(n + 1);
            for (int i = sz; i <= n; ++i) pows[i] = base * pows[i - 1];
        }
    private:
        static inline std::vector<mint> pows { 1 };
        static inline mint base = base_as_int;
        static constexpr int mod = mint::mod();
    };

    template <typename mint>
    struct pow_mods {
        pow_mods() = default;
        pow_mods(mint base, int n) : base(base) { ensure(n); }
        const mint& operator[](int i) const {
            ensure(i);
            return pows[i];
        }
        void ensure(int n) const {
            int sz = pows.size();
            if (sz > n) return;
            pows.resize(n + 1);
            for (int i = sz; i <= n; ++i) pows[i] = base * pows[i - 1];
        }
    private:
        mutable std::vector<mint> pows { 1 };
        mint base;
        static constexpr int mod = mint::mod();
    };
}

#include <cassert>

namespace suisen {
    template <typename T, typename U = T>
    struct factorial {
        factorial() = default;
        factorial(int n) { ensure(n); }

        static void ensure(const int n) {
            int sz = _fac.size();
            if (n + 1 <= sz) return;
            int new_size = std::max(n + 1, sz * 2);
            _fac.resize(new_size), _fac_inv.resize(new_size);
            for (int i = sz; i < new_size; ++i) _fac[i] = _fac[i - 1] * i;
            _fac_inv[new_size - 1] = U(1) / _fac[new_size - 1];
            for (int i = new_size - 1; i > sz; --i) _fac_inv[i - 1] = _fac_inv[i] * i;
        }

        T fac(const int i) {
            ensure(i);
            return _fac[i];
        }
        T operator()(int i) {
            return fac(i);
        }
        U fac_inv(const int i) {
            ensure(i);
            return _fac_inv[i];
        }
        U binom(const int n, const int r) {
            if (n < 0 or r < 0 or n < r) return 0;
            ensure(n);
            return _fac[n] * _fac_inv[r] * _fac_inv[n - r];
        }
        U perm(const int n, const int r) {
            if (n < 0 or r < 0 or n < r) return 0;
            ensure(n);
            return _fac[n] * _fac_inv[n - r];
        }
    private:
        static std::vector<T> _fac;
        static std::vector<U> _fac_inv;
    };
    template <typename T, typename U>
    std::vector<T> factorial<T, U>::_fac{ 1 };
    template <typename T, typename U>
    std::vector<U> factorial<T, U>::_fac_inv{ 1 };
} // namespace suisen

namespace suisen {
    // {n,m} in qs: Sum[i=0,n] r^i Binom[m,i]
    template <typename Mint>
    std::vector<Mint> binom_sum_prefix(const std::vector<std::pair<int, int>>& qs, const Mint& r = 1) {
        const int q = qs.size();
        std::vector<Mint> res(qs.size());

        if (r == -1) {
            factorial<Mint> fac;
            for (int i = 0; i < q; ++i) {
                auto [n, m] = qs[i];
                n = std::min(n, m);
                if (n < 0) {
                    res[i] = 0;
                } else if (m == 0) {
                    // n = m = 0
                    res[i] = 1;
                } else {
                    res[i] = (n % 2 == 1 ? -1 : +1) * fac.binom(m - 1, n);
                }
            }
            return res;
        }

        std::vector<int> qid;
        std::vector<std::pair<int, int>> ranges;
        qid.reserve(q), ranges.reserve(q);
        int max_m = 1;
        for (int i = 0; i < q; ++i) {
            auto [n, m] = qs[i];
            n = std::min(n, m);
            if (n < 0) {
                res[i] = 0;
            } else if (m == 0) {
                // n = m = 0
                res[i] = 1;
            } else {
                qid.push_back(i);
                ranges.emplace_back(n, m);
                max_m = std::max(max_m, m);
            }
        }
        pow_mods<Mint> pow_r(r, max_m + 1);
        factorial<Mint> fac(max_m + 1);
        const Mint inv_r1 = (r + 1).inv();

        Mo mo(max_m, std::move(ranges));
        Mint sum = 1;
        const std::vector<Mint> res_mo = mo.solve(
            [&] {
                return sum;
            },
            [&](const int n) { // Add Left
                const int m = mo.get_right();
                // (n + 1, m) -> (n, m)
                sum -= pow_r[n + 1] * fac.binom(m, n + 1);
            },
            [&](const int n) { // Del Left
                const int m = mo.get_right();
                // (n, m) -> (n + 1, m)
                sum += pow_r[n + 1] * fac.binom(m, n + 1);
            },
            [&](const int m) { // Add Right
                const int n = mo.get_left();
                // (n, m) -> (n, m + 1)
                sum = (r + 1) * sum - pow_r[n + 1] * fac.binom(m, n);
            },
            [&](const int m) { // Del Right
                const int n = mo.get_left();
                // (n, m + 1) -> (n, m)
                sum = (pow_r[n + 1] * fac.binom(m, n) + sum) * inv_r1;
            }
        );
        for (int i = 0; i < int(qid.size()); ++i) res[qid[i]] = res_mo[i];
        return res;
    }

    // {a,b,m} in qs: Sum[i=a,b] r^i Binom[m,i]
    template <typename Mint>
    std::vector<Mint> binom_sum(const std::vector<std::tuple<int, int, int>>& qs, const Mint& r = 1) {
        const int q = qs.size();
        std::vector<std::pair<int, int>> ls(q), rs(q);
        for (int i = 0; i < q; ++i) {
            const auto [a, b, m] = qs[i];
            ls[i] = { a - 1, m };
            rs[i] = { b, m };
        }
        std::vector<Mint> suml = binom_sum_prefix(ls, r);
        std::vector<Mint> sumr = binom_sum_prefix(rs, r);
        std::vector<Mint> sum(q);
        for (int i = 0; i < q; ++i) sum[i] = sumr[i] - suml[i];
        return sum;
    }
} // namespace suisen

#include <iostream>

#include <atcoder/modint>

using mint = atcoder::modint998244353;

constexpr int M = 400010;

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

    int q;
    std::cin >> q;

    std::vector<std::pair<int, int>> qs(q);
    for (int i = 0; i < q; ++i) {
        int n, m;
        std::cin >> n >> m;
        qs[i] = { n, 2 * m };
    }

    const mint inv2 = mint(2).inv();
    suisen::pow_mods<mint> pw(-inv2, 200010);

    std::vector<mint> res = suisen::binom_sum_prefix<mint>(qs, -2);
    for (int i = 0; i < q; ++i) {
        auto [n, m] = qs[i];
        std::cout << ((res[i] - 1) * -pw[n + 1]).val() << '\n';
    }

    return 0;
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード