結果
| 問題 | No.1720 Division Permutation |
| ユーザー |
👑  rin204
|
| 提出日時 | 2024-05-06 14:58:32 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 60 |
ソースコード
#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;elsex = (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;elsex = (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 PerTreeRangeAddRangeMinstruct 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 oru.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;}