#979297 (C++23) No.1720 Division Permutation

提出ソース

結果

問題	No.1720 Division Permutation
ユーザー	👑 rin204
提出日時	2024-05-06 14:58:32
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	287 ms / 4,000 ms
コード長	14,607 bytes
コンパイル時間	3,429 ms
コンパイル使用メモリ	268,288 KB
実行使用メモリ	34,244 KB
最終ジャッジ日時	2024-11-28 22:19:25
合計ジャッジ時間	15,935 ms
ジャッジサーバーID （参考情報）	judge5 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,820 KB
testcase_02	AC	2 ms 6,820 KB
testcase_03	AC	1 ms 6,816 KB
testcase_04	AC	2 ms 6,820 KB
testcase_05	AC	2 ms 6,820 KB
testcase_06	AC	2 ms 6,816 KB
testcase_07	AC	2 ms 6,816 KB
testcase_08	AC	1 ms 6,816 KB
testcase_09	AC	1 ms 6,816 KB
testcase_10	AC	2 ms 6,816 KB
testcase_11	AC	1 ms 6,820 KB
testcase_12	AC	1 ms 6,816 KB
testcase_13	AC	283 ms 32,752 KB
testcase_14	AC	276 ms 33,040 KB
testcase_15	AC	171 ms 21,284 KB
testcase_16	AC	277 ms 31,940 KB
testcase_17	AC	187 ms 22,788 KB
testcase_18	AC	188 ms 33,444 KB
testcase_19	AC	265 ms 33,712 KB
testcase_20	AC	280 ms 32,992 KB
testcase_21	AC	271 ms 33,520 KB
testcase_22	AC	270 ms 33,556 KB
testcase_23	AC	266 ms 32,628 KB
testcase_24	AC	278 ms 34,244 KB
testcase_25	AC	264 ms 33,136 KB
testcase_26	AC	268 ms 32,808 KB
testcase_27	AC	280 ms 32,988 KB
testcase_28	AC	264 ms 32,980 KB
testcase_29	AC	273 ms 34,068 KB
testcase_30	AC	269 ms 33,812 KB
testcase_31	AC	276 ms 32,968 KB
testcase_32	AC	2 ms 6,820 KB
testcase_33	AC	2 ms 6,816 KB
testcase_34	AC	2 ms 6,820 KB
testcase_35	AC	1 ms 6,816 KB
testcase_36	AC	1 ms 6,816 KB
testcase_37	AC	2 ms 6,816 KB
testcase_38	AC	1 ms 6,816 KB
testcase_39	AC	1 ms 6,820 KB
testcase_40	AC	2 ms 6,816 KB
testcase_41	AC	2 ms 6,820 KB
testcase_42	AC	2 ms 6,820 KB
testcase_43	AC	237 ms 28,468 KB
testcase_44	AC	220 ms 26,804 KB
testcase_45	AC	204 ms 24,368 KB
testcase_46	AC	144 ms 20,164 KB
testcase_47	AC	201 ms 24,872 KB
testcase_48	AC	160 ms 20,504 KB
testcase_49	AC	244 ms 29,344 KB
testcase_50	AC	214 ms 24,492 KB
testcase_51	AC	163 ms 20,296 KB
testcase_52	AC	223 ms 27,600 KB
testcase_53	AC	277 ms 33,012 KB
testcase_54	AC	287 ms 33,100 KB
testcase_55	AC	273 ms 33,804 KB
testcase_56	AC	282 ms 33,616 KB
testcase_57	AC	279 ms 32,432 KB
testcase_58	AC	276 ms 32,272 KB
testcase_59	AC	271 ms 33,952 KB
testcase_60	AC	275 ms 32,352 KB
testcase_61	AC	280 ms 32,728 KB
testcase_62	AC	276 ms 32,876 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;

template <int MOD>
struct Modint {
    int x;
    Modint() : x(0) {}
    Modint(int64_t y) {
        if (y >= 0)
            x = y % MOD;
        else
            x = (y % MOD + MOD) % MOD;
    }

    Modint &operator+=(const Modint &p) {
        x += p.x;
        if (x >= MOD) x -= MOD;
        return *this;
    }

    Modint &operator-=(const Modint &p) {
        x -= p.x;
        if (x < 0) x += MOD;
        return *this;
    }

    Modint &operator*=(const Modint &p) {
        x = int(1LL * x * p.x % MOD);
        return *this;
    }

    Modint &operator/=(const Modint &p) {
        *this *= p.inverse();
        return *this;
    }

    Modint &operator%=(const Modint &p) {
        assert(p.x == 0);
        return *this;
    }

    Modint operator-() const {
        return Modint(-x);
    }

    Modint &operator++() {
        x++;
        if (x == MOD) x = 0;
        return *this;
    }

    Modint &operator--() {
        if (x == 0) x = MOD;
        x--;
        return *this;
    }

    Modint operator++(int) {
        Modint result = *this;
        ++*this;
        return result;
    }

    Modint operator--(int) {
        Modint result = *this;
        --*this;
        return result;
    }

    friend Modint operator+(const Modint &lhs, const Modint &rhs) {
        return Modint(lhs) += rhs;
    }

    friend Modint operator-(const Modint &lhs, const Modint &rhs) {
        return Modint(lhs) -= rhs;
    }

    friend Modint operator*(const Modint &lhs, const Modint &rhs) {
        return Modint(lhs) *= rhs;
    }

    friend Modint operator/(const Modint &lhs, const Modint &rhs) {
        return Modint(lhs) /= rhs;
    }

    friend Modint operator%(const Modint &lhs, const Modint &rhs) {
        assert(rhs.x == 0);
        return Modint(lhs);
    }

    bool operator==(const Modint &p) const {
        return x == p.x;
    }

    bool operator!=(const Modint &p) const {
        return x != p.x;
    }

    bool operator<(const Modint &rhs) const {
        return x < rhs.x;
    }

    bool operator<=(const Modint &rhs) const {
        return x <= rhs.x;
    }

    bool operator>(const Modint &rhs) const {
        return x > rhs.x;
    }

    bool operator>=(const Modint &rhs) const {
        return x >= rhs.x;
    }

    Modint inverse() const {
        int a = x, b = MOD, u = 1, v = 0, t;
        while (b > 0) {
            t = a / b;
            a -= t * b;
            u -= t * v;
            std::swap(a, b);
            std::swap(u, v);
        }
        return Modint(u);
    }

    Modint pow(int64_t k) const {
        Modint ret(1);
        Modint y(x);
        while (k > 0) {
            if (k & 1) ret *= y;
            y *= y;
            k >>= 1;
        }
        return ret;
    }

    friend std::ostream &operator<<(std::ostream &os, const Modint &p) {
        return os << p.x;
    }

    friend std::istream &operator>>(std::istream &is, Modint &p) {
        int64_t y;
        is >> y;
        p = Modint<MOD>(y);
        return (is);
    }

    static int get_mod() {
        return MOD;
    }
};

struct Arbitrary_Modint {
    int x;
    static int MOD;

    static void set_mod(int mod) {
        MOD = mod;
    }

    Arbitrary_Modint() : x(0) {}
    Arbitrary_Modint(int64_t y) {
        if (y >= 0)
            x = y % MOD;
        else
            x = (y % MOD + MOD) % MOD;
    }

    Arbitrary_Modint &operator+=(const Arbitrary_Modint &p) {
        x += p.x;
        if (x >= MOD) x -= MOD;
        return *this;
    }

    Arbitrary_Modint &operator-=(const Arbitrary_Modint &p) {
        x -= p.x;
        if (x < 0) x += MOD;
        return *this;
    }

    Arbitrary_Modint &operator*=(const Arbitrary_Modint &p) {
        x = int(1LL * x * p.x % MOD);
        return *this;
    }

    Arbitrary_Modint &operator/=(const Arbitrary_Modint &p) {
        *this *= p.inverse();
        return *this;
    }

    Arbitrary_Modint &operator%=(const Arbitrary_Modint &p) {
        assert(p.x == 0);
        return *this;
    }

    Arbitrary_Modint operator-() const {
        return Arbitrary_Modint(-x);
    }

    Arbitrary_Modint &operator++() {
        x++;
        if (x == MOD) x = 0;
        return *this;
    }

    Arbitrary_Modint &operator--() {
        if (x == 0) x = MOD;
        x--;
        return *this;
    }

    Arbitrary_Modint operator++(int) {
        Arbitrary_Modint result = *this;
        ++*this;
        return result;
    }

    Arbitrary_Modint operator--(int) {
        Arbitrary_Modint result = *this;
        --*this;
        return result;
    }

    friend Arbitrary_Modint operator+(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs) {
        return Arbitrary_Modint(lhs) += rhs;
    }

    friend Arbitrary_Modint operator-(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs) {
        return Arbitrary_Modint(lhs) -= rhs;
    }

    friend Arbitrary_Modint operator*(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs) {
        return Arbitrary_Modint(lhs) *= rhs;
    }

    friend Arbitrary_Modint operator/(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs) {
        return Arbitrary_Modint(lhs) /= rhs;
    }

    friend Arbitrary_Modint operator%(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs) {
        assert(rhs.x == 0);
        return Arbitrary_Modint(lhs);
    }

    bool operator==(const Arbitrary_Modint &p) const {
        return x == p.x;
    }

    bool operator!=(const Arbitrary_Modint &p) const {
        return x != p.x;
    }

    bool operator<(const Arbitrary_Modint &rhs) {
        return x < rhs.x;
    }

    bool operator<=(const Arbitrary_Modint &rhs) {
        return x <= rhs.x;
    }

    bool operator>(const Arbitrary_Modint &rhs) {
        return x > rhs.x;
    }

    bool operator>=(const Arbitrary_Modint &rhs) {
        return x >= rhs.x;
    }

    Arbitrary_Modint inverse() const {
        int a = x, b = MOD, u = 1, v = 0, t;
        while (b > 0) {
            t = a / b;
            a -= t * b;
            u -= t * v;
            std::swap(a, b);
            std::swap(u, v);
        }
        return Arbitrary_Modint(u);
    }

    Arbitrary_Modint pow(int64_t k) const {
        Arbitrary_Modint ret(1);
        Arbitrary_Modint y(x);
        while (k > 0) {
            if (k & 1) ret *= y;
            y *= y;
            k >>= 1;
        }
        return ret;
    }

    friend std::ostream &operator<<(std::ostream &os, const Arbitrary_Modint &p) {
        return os << p.x;
    }

    friend std::istream &operator>>(std::istream &is, Arbitrary_Modint &p) {
        int64_t y;
        is >> y;
        p = Arbitrary_Modint(y);
        return (is);
    }

    static int get_mod() {
        return MOD;
    }
};
int Arbitrary_Modint::MOD = 998244353;

using modint9 = Modint<998244353>;
using modint1 = Modint<1000000007>;
using modint  = Arbitrary_Modint;

template <class S, S (*op)(S, S), S (*e)(), class F, S (*mapping)(F, S), F (*composition)(F, F),
          F (*id)()>
struct lazy_segtree {
  public:
    explicit lazy_segtree(const std::vector<S> &v) : _n(int(v.size())) {
        size = 1;
        log  = 0;
        while (size < _n) {
            log++;
            size <<= 1;
        }
        d  = std::vector<S>(2 * size, e());
        lz = std::vector<F>(size, id());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) update(i);
    }
    explicit lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}

    S prod(int l, int r) {
        if (l == r) return e();

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        S sml = e(), smr = e();
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

    S get(int x) {
        return prod(x, x + 1);
    }

    S all_prod() {
        return d[1];
    }

    void apply(int l, int r, F f) {
        if (l == r) return;

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply(l++, f);
                if (r & 1) all_apply(--r, f);
                l >>= 1;
                r >>= 1;
            }
            l = l2;
            r = r2;
        }

        for (int i = 1; i <= log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }

  private:
    int _n, size, log;
    std::vector<S> d;
    std::vector<F> lz;
    void update(int k) {
        d[k] = op(d[2 * k], d[2 * k + 1]);
    }
    void all_apply(int k, F f) {
        d[k] = mapping(f, d[k]);
        if (k < size) lz[k] = composition(f, lz[k]);
    }
    void push(int k) {
        all_apply(2 * k, lz[k]);
        all_apply(2 * k + 1, lz[k]);
        lz[k] = id();
    }
};

namespace PerTreeRangeAddRangeMin {
using S = int;
S op(S l, S r) {
    return l < r ? l : r;
}
S e() {
    return 1 << 30;
}
using F = int;
S mapping(F f, S x) {
    return f + x;
}
F composition(F f, F g) {
    return f + g;
}
F id() {
    return 0;
}

using SEG = lazy_segtree<S, op, e, F, mapping, composition, id>;
} // namespace PerTreeRangeAddRangeMin

struct PermutationTree {
    enum NodeType {
        JOIN_ASC,
        JOIN_DESC,
        CUT,
        LEAF,
        NONE,
    };

    struct Node {
        NodeType tp;
        int l, r;
        int x_min, x_max;
        std::vector<int> child;
        int size() {
            return r - l;
        }
    };

    int root;
    std::vector<int> P;
    std::vector<Node> nodes;

    PermutationTree() : root(-1) {}
    PermutationTree(const std::vector<int> &P) : root(-1), P(P) {
        assert(!P.empty());
        build();
    }

  private:
    void add_child(int par, int chi) {
        nodes[par].child.push_back(chi);
        nodes[par].l     = std::min(nodes[par].l, nodes[chi].l);
        nodes[par].r     = std::max(nodes[par].r, nodes[chi].r);
        nodes[par].x_min = std::min(nodes[par].x_min, nodes[chi].x_min);
        nodes[par].x_max = std::max(nodes[par].x_max, nodes[chi].x_max);
    }

    void build() {
        PerTreeRangeAddRangeMin::SEG seg((std::vector<int>(P.size())));

        std::stack<int> hi, lo;
        hi.push(-1);
        lo.push(-1);
        std::stack<int> st;
        for (int i = 0; i < int(P.size()); i++) {
            while (hi.size() >= 2 and P[i] > P[hi.top()]) {
                auto hi_fi = hi.top();
                hi.pop();
                auto hi_se = hi.empty() ? -1 : hi.top();
                seg.apply(hi_se + 1, hi_fi + 1, P[i] - P[hi_fi]);
            }
            hi.push(i);

            while (lo.size() >= 2 and P[i] < P[lo.top()]) {
                auto lo_fi = lo.top();
                lo.pop();
                auto lo_se = lo.empty() ? -1 : lo.top();
                seg.apply(lo_se + 1, lo_fi + 1, P[lo_fi] - P[i]);
            }
            lo.push(i);

            int h = nodes.size();
            nodes.push_back({NodeType::LEAF, i, i + 1, P[i], P[i], std::vector<int>()});

            while (1) {
                NodeType join_tp = NodeType::NONE;
                if (!st.empty() and nodes[st.top()].x_max + 1 == nodes[h].x_min) {
                    join_tp = NodeType::JOIN_ASC;
                } else if (!st.empty() and nodes[h].x_max + 1 == nodes[st.top()].x_min) {
                    join_tp = NodeType::JOIN_DESC;
                }

                if (!st.empty() and join_tp != NodeType::NONE) {
                    const Node &vtp = nodes[st.top()];
                    if (join_tp == vtp.tp) {
                        add_child(st.top(), h);
                        h = st.top();
                        st.pop();
                    } else {
                        int j = st.top();
                        nodes.push_back(
                            {join_tp, nodes[j].l, nodes[j].r, nodes[j].x_min, nodes[j].x_max, {j}});
                        st.pop();
                        add_child(nodes.size() - 1, h);
                        h = nodes.size() - 1;
                    }
                } else if (seg.prod(0, i + 1 - nodes[h].size()) == 0) {
                    int l     = nodes[h].l;
                    int r     = nodes[h].r;
                    int x_max = nodes[h].x_max;
                    int x_min = nodes[h].x_min;
                    nodes.push_back({NodeType::CUT, l, r, x_min, x_max, {h}});
                    h = nodes.size() - 1;

                    do {
                        add_child(h, st.top());
                        st.pop();
                    } while (nodes[h].x_max - nodes[h].x_min + 1 != nodes[h].size());
                    std::reverse(nodes[h].child.begin(), nodes[h].child.end());
                } else {
                    break;
                }
            }
            st.push(h);
            seg.apply(0, i + 1, -1);
        }
        assert(st.size() == 1);
        root = st.top();
    }
};
using mint = modint9;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> P(n);
    for (int i = 0; i < n; i++) {
        cin >> P[i];
        P[i]--;
    }
    PermutationTree pt(P);
    vector<vector<mint>> dp(n + 1, vector<mint>(k + 1, 0));
    dp[0][0] = 1;

    auto dfs = [&](auto &&self, int pos) -> void {
        auto &u = pt.nodes[pos];
        if (u.tp == PermutationTree::NodeType::LEAF or u.tp == PermutationTree::NodeType::CUT) {
            for (int i = 0; i < k; i++) {
                dp[u.r][i + 1] += dp[u.l][i];
            }
        }

        vector<mint> add(k, 0);

        for (auto npos : u.child) {
            self(self, npos);
            auto &v = pt.nodes[npos];
            if (u.tp == PermutationTree::NodeType::JOIN_ASC or
                u.tp == PermutationTree::NodeType::JOIN_DESC) {
                for (int i = 0; i < k; i++) {
                    dp[v.r][i + 1] += add[i];
                    add[i] += dp[v.l][i];
                }
            }
        }
    };

    dfs(dfs, pt.root);

    for (int i = 1; i <= k; i++) {
        cout << dp[n][i] << endl;
    }
}

int main() {
    // cin.tie(0)->sync_with_stdio(0);
    int t;
    t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

yukicoder

結果

テストケース

ソースコード