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

• 問題: No.1720 Division Permutation
• ユーザー: noya2
• 提出日時: 2026-11-11 02:44:49
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 86 ms / 4,000 ms
• コード長: 5,839 bytes
• コンパイル時間: 3,955 ms
• コンパイル使用メモリ: 364,164 KB
• 実行使用メモリ: 26,088 KB
• 最終ジャッジ日時: 2026-11-11 02:45:10
• 合計ジャッジ時間: 10,657 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
sample	AC * 3
other	AC * 59

ソースコード

#include<bits/stdc++.h>
#define rep(i,s,n) for (int i = (int)(s); i < (int)(n); i++)
#define all(v) begin(v),end(v)
using namespace std;
using ll = long long;
bool chmin(auto &a, auto b){ return a > b ? a = b, 1 : 0; }
bool chmax(auto &a, auto b){ return a < b ? a = b, 1 : 0; }
template<typename T>
ostream &operator<<(ostream &os, const vector<T> &a){
    rep(i, 0, a.size()) os << (i ? " " : "") << a[i];
    return os;
}

void dump(auto ...vs){
    ((cerr << vs << ' '), ...) << endl;
}

struct PermutationTree {
  enum Type { Prime, Inc, Dec, Leaf };
  struct Node { int parent; Type type; int l, r; };
  vector<Node> tree;
  PermutationTree(vector<int> p) {
    int n = p.size();
    vector<int> q(n);
    rep(i, 0, n) q[p[i]] = i;
    vector<vector<int>> mn(bit_width((unsigned)n), q);
    rep(k, 1, mn.size()) rep(i, 0, n - (1 << k) + 1)
        mn[k][i] = min(mn[k - 1][i], mn[k - 1][i + (1 << (k - 1))]);
    auto rmq = [&](int l, int r) {
      int k = bit_width((unsigned)(r - l)) - 1;
      return min(mn[k][l], mn[k][r - (1 << k)]);
    };
    struct Base { int l, lo, hi; };
    vector<Base> st;
    vector<pair<int,int>> coms;
    rep(r, 1, n + 1) {
      Base b{r - 1, p[r - 1], p[r - 1] + 1};
      while(st.size()) {
        st.back().lo = min(st.back().lo, b.lo);
        st.back().hi = max(st.back().hi, b.hi);
        auto x = st.back();
        if(rmq(x.lo, x.hi) < x.l) {
          st.pop_back();
          st.back().lo = min(st.back().lo, x.lo);
          st.back().hi = max(st.back().hi, x.hi);
        } else if(x.hi - x.lo == r - x.l) {
          b = x; st.pop_back();
          coms.emplace_back(x.l, r);
        } else break;
      }
      st.push_back(b);
    }
    while(st.size() > 1) {
      auto x = st.back(); st.pop_back();
      auto& y = st.back();
      y.lo = min(y.lo, x.lo);
      y.hi = max(y.hi, x.hi);
      if(y.hi - y.lo == n - y.l) coms.emplace_back(y.l, n);
    }
    if(st.size() != 1) coms.emplace_back(0, n);
    rep(i, 0, n) tree.push_back({-1, Leaf, i, i + 1});
    vector<int> id(n), nxt(n);
    iota(all(id), 0);
    rep(i, 0, n) nxt[i] = i + 1;
    for(auto [l, r] : coms) {
      int m = nxt[l];
      if(nxt[m] == r) {
        int a = id[l], b = id[m];
        nxt[l] = r;
        Type t = p[l] < p[r - 1] ? Inc : Dec;
        if(tree[a].type == t) {
          tree[b].parent = a;
          tree[a].r = r;
        } else {
          int c = tree.size();
          tree.push_back({-1, t, l, r});
          tree[a].parent = tree[b].parent = c;
          id[l] = c;
        }
      } else {
        int c = tree.size();
        tree.push_back({-1, Prime, l, r});
        for(int i = l; i < r; i = nxt[i]) tree[id[i]].parent = c;
        id[l] = c;
        nxt[l] = r;
      }
    }
  }
};

template<int m> struct mm {
  uint32_t x;
  mm() : x(0) {}
  template<signed_integral T> mm(T a) : x(a % m) {
    if(x >= m) x += m;  // x is unsigned, (x < 0) <=> (x >= mod)
  }
  template<unsigned_integral T> mm(T a) : x(a % m) {}
  friend mm operator+(mm a, mm b) {
    a.x += b.x;
    if(a.x >= m) a.x -= m;
    return a;
  }
  friend mm operator-(mm a, mm b) {
    a.x -= b.x;
    if(a.x >= m) a.x += m;  // a.x < 0, a.x [[+=]] m
    return a;
  }
  friend mm operator*(mm a, mm b) { return (uint64_t)a.x * b.x; }
  mm pow(ll n) const {
    mm a = *this, ret = 1;
    while(n) {
      if(n & 1) ret *= a;
      a *= a;
      n >>= 1;
    }
    return ret;
  }
  mm inv() const { return pow(m - 2); }
  friend mm operator/(mm a, mm b) { return a * b.inv(); }
  mm operator-() const { return mm(0) - *this; }
  bool operator==(mm b) const { return x == b.x; }
  friend mm& operator+=(mm& a, mm b) { return a = a + b; }
  friend mm& operator-=(mm& a, mm b) { return a = a - b; }
  friend mm& operator*=(mm& a, mm b) { return a = a * b; }
  friend mm& operator/=(mm& a, mm b) { return a = a * b.inv(); }
  static int mod() { return m; }
  friend ostream &operator<<(ostream &os, const mm &a){
    return os << a.x;
  }
};

using mint = mm<998244353>;

void solve(){
    int n, k; cin >> n >> k;
    vector<int> p(n);
    rep(i,0,n){
        cin >> p[i];
        --p[i];
    }
    PermutationTree pt(p);
    auto nodes = pt.tree;
    int sz = nodes.size();
    vector<vector<int>> g(sz);
    int root = -1;
    rep(i,0,sz){
        int par = nodes[i].parent;
        if (par != -1){
            g[par].emplace_back(i);
        }
        else {
            root = i;
        }
    }
    rep(i,0,sz){
        ranges::sort(g[i],{},[&](int v){
            return nodes[v].l;
        });
    }
    using ar = array<mint,11>;
    using PT = PermutationTree;
    auto dfs = [&](auto sfs, int v) -> ar {
        if (nodes[v].type == PT::Leaf){
            ar dp = {};
            dp[1] = 1;
            return dp;
        }
        if (nodes[v].type == PT::Prime){
            ar dp = {};
            dp[0] = 1;
            for (int u : g[v]){
                auto ep = sfs(sfs,u);
                ar ndp = {};
                rep(i,0,k) rep(j,1,k+1-i){
                    ndp[i+j] += dp[i] * ep[j];
                }
                swap(dp,ndp);
            }
            dp[1] += 1;
            return dp;
        }
        ar dp = {};
        dp[0] = 1;
        ar rui = {};
        for (int u : g[v]){
            auto ep = sfs(sfs,u);
            ar ndp = {};
            rep(i,0,k) rep(j,1,k+1-i){
                ndp[i+j] += dp[i] * ep[j];
            }
            rep(i,0,k){
                ndp[i+1] += rui[i];
            }
            rep(i,0,k+1){
                rui[i] += dp[i];
            }
            swap(dp,ndp);
        }
        // dump(nodes[v].l,nodes[v].r,":",ranges::to<vector<mint>>(dp));
        return dp;
    };
    auto dp = dfs(dfs,root);
    rep(i,1,k+1){
        cout << dp[i].x << '\n';
    }
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    solve();    
}