結果

問題 No.1720 Division Permutation
ユーザー 👑 rin204rin204
提出日時 2024-05-06 14:58:32
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 313 ms / 4,000 ms
コード長 14,607 bytes
コンパイル時間 3,655 ms
コンパイル使用メモリ 266,540 KB
実行使用メモリ 32,664 KB
最終ジャッジ日時 2024-05-06 14:58:50
合計ジャッジ時間 15,935 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 3 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 3 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 294 ms
32,080 KB
testcase_14 AC 313 ms
32,336 KB
testcase_15 AC 171 ms
21,256 KB
testcase_16 AC 276 ms
31,132 KB
testcase_17 AC 193 ms
22,560 KB
testcase_18 AC 216 ms
32,200 KB
testcase_19 AC 293 ms
32,660 KB
testcase_20 AC 288 ms
32,664 KB
testcase_21 AC 282 ms
32,400 KB
testcase_22 AC 277 ms
32,532 KB
testcase_23 AC 273 ms
32,528 KB
testcase_24 AC 286 ms
32,664 KB
testcase_25 AC 298 ms
32,400 KB
testcase_26 AC 282 ms
32,404 KB
testcase_27 AC 299 ms
32,656 KB
testcase_28 AC 294 ms
32,528 KB
testcase_29 AC 283 ms
32,528 KB
testcase_30 AC 283 ms
32,656 KB
testcase_31 AC 284 ms
32,660 KB
testcase_32 AC 1 ms
5,376 KB
testcase_33 AC 2 ms
5,376 KB
testcase_34 AC 2 ms
5,376 KB
testcase_35 AC 2 ms
5,376 KB
testcase_36 AC 1 ms
5,376 KB
testcase_37 AC 2 ms
5,376 KB
testcase_38 AC 2 ms
5,376 KB
testcase_39 AC 1 ms
5,376 KB
testcase_40 AC 2 ms
5,376 KB
testcase_41 AC 2 ms
5,376 KB
testcase_42 AC 2 ms
5,376 KB
testcase_43 AC 246 ms
28,116 KB
testcase_44 AC 231 ms
26,200 KB
testcase_45 AC 206 ms
24,072 KB
testcase_46 AC 148 ms
19,236 KB
testcase_47 AC 211 ms
24,760 KB
testcase_48 AC 165 ms
20,376 KB
testcase_49 AC 258 ms
29,184 KB
testcase_50 AC 202 ms
23,820 KB
testcase_51 AC 179 ms
20,424 KB
testcase_52 AC 233 ms
26,596 KB
testcase_53 AC 287 ms
32,376 KB
testcase_54 AC 287 ms
32,088 KB
testcase_55 AC 283 ms
32,224 KB
testcase_56 AC 293 ms
32,300 KB
testcase_57 AC 297 ms
32,088 KB
testcase_58 AC 303 ms
32,252 KB
testcase_59 AC 298 ms
32,200 KB
testcase_60 AC 290 ms
32,084 KB
testcase_61 AC 291 ms
32,408 KB
testcase_62 AC 289 ms
32,224 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0