#969166 (C++17) No.1392 Don't be together

提出ソース

結果

問題	No.1392 Don't be together
ユーザー	00 Sakuda
提出日時	2024-04-05 01:51:38
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	MLE
実行時間	-
コード長	9,736 bytes
コンパイル時間	2,927 ms
コンパイル使用メモリ	238,396 KB
実行使用メモリ	814,848 KB
最終ジャッジ日時	2024-10-01 00:44:30
合計ジャッジ時間	5,002 ms
ジャッジサーバーID （参考情報）	judge1 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	1 ms 5,248 KB
testcase_02	AC	1 ms 5,248 KB
testcase_03	AC	1 ms 5,248 KB
testcase_04	AC	1 ms 5,248 KB
testcase_05	AC	1 ms 5,248 KB
testcase_06	MLE	-
testcase_07	--	-
testcase_08	--	-
testcase_09	--	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-

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

ソースコード

raw source code

#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <bitset>
#include <iomanip>
using namespace std;
using ll = long long;
using VVI = vector<vector<int>>;
using VVL = vector<vector<ll>>;
using VI = vector<int>;
using VL = vector<ll>;
using VS = vector<string>;
using VC = vector<char>;
using VP = vector<pair<int, int>>;
using Graph0 = vector<vector<int>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define drep(i, a, b) for (int i = (int)(a);i >= (int)(b);i--)
#define urep(i, a, b) for (int i = (int)(a);i <= (int)(b);i++)
#define lrep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define ldrep(i, a, b) for (ll i = (ll)(a);i >= (ll)(b);i--)
#define lurep(i, a, b) for (ll i = (ll)(a);i <= (ll)(b);i++)
#define arep(i, v) for (auto i : v)
#define all(a) (a).begin(), (a).end()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define eyes cout << "Yes" << endl;exit(0);
#define eno cout << "No" << endl;exit(0);
template <typename T>
bool chmax(T &a, const T& b) {
  if (a < b) {
    a = b;  
    return true;
  }
  return false;
}
template <typename T>
bool chmin(T &a, const T& b) {
  if (a > b) {
    a = b; 
    return true;
  }
  return false;
}
template<typename T>
void excout(T A) {
  cout << A << endl;
  exit(0);
}
constexpr long long INF = (1LL << 60); // INFにちゅういい！

// 辺の情報
struct Edge
{
  // 行先
  int to;

  // コスト
  int cost;
};

using Graph = std::vector<std::vector<Edge>>;

// { distance, from }
using Pair = std::pair<long long, int>;

// ダイクストラ法 (1.1 基本実装)
// distances は頂点数と同じサイズ, 全要素 INF で初期化しておく
void Dijkstra(const Graph& graph, std::vector<long long>& distances, int startIndex)
{
  // 「現時点での最短距離, 頂点」の順に取り出す priority_queue
  // デフォルトの priority_queue は降順に取り出すため std::greater を使う
  std::priority_queue<Pair, std::vector<Pair>, std::greater<Pair>> q;
  q.emplace((distances[startIndex] = 0), startIndex);

  while (!q.empty())
  {
    const long long distance = q.top().first;
    const int from = q.top().second;
    q.pop();

    // 最短距離でなければ処理しない
    if (distances[from] < distance)
    {
      continue;
    }

    // 現在の頂点からの各辺について
    for (const auto& edge : graph[from])
    {
      // to までの新しい距離
      const long long d = (distances[from] + edge.cost);

      // d が現在の記録より小さければ更新
      if (d < distances[edge.to])
      {
        q.emplace((distances[edge.to] = d), edge.to);
      }
    }
  }
}
template<typename T>
T MODS(T a, T mods) {
  return ((((((a + mods) % mods) + mods) % mods)));
}
//combination 列挙用 --int ver
VVI comb(int n, int r) {
  VVI v(n + 1, VI (n + 1, 0));
  for (int i = 0; i < v.size(); i++) {
    v[i][0] = 1;
    v[i][i] = 1;
  }
  for (int j = 1; j < v.size(); j++) {
    for (int k = 1; k < j; k++) {
      v[j][k] = (v[j - 1][k - 1] + v[j - 1][k]);
    }
  }
  return v;
}
vector<pair<long long, long long> > prime_factorize(long long N) {
    // 答えを表す可変長配列
    vector<pair<long long, long long> > res;

    // √N まで試し割っていく
    for (long long p = 2; p * p <= N; ++p) {
        // N が p で割り切れないならばスキップ
        if (N % p != 0) {
            continue;
        }

        // N の素因数 p に対する指数を求める
        int e = 0;
        while (N % p == 0) {
            // 指数を 1 増やす
            ++e;

            // N を p で割る
            N /= p;
        }

        // 答えに追加
        res.emplace_back(p, e);
    }

    // 素数が最後に残ることがありうる
    if (N != 1) {
        res.emplace_back(N, 1);
    }
    return res;
}
using UNION_TYPE = int;
struct UnionFind {
    vector<UNION_TYPE> par, siz;
    UnionFind(UNION_TYPE n) : par(n, -1), siz(n, 1) {}
    UNION_TYPE root(UNION_TYPE x) {
        if (par[x] == -1) return x;
        else return par[x] = root(par[x]);
    }
    bool issame(UNION_TYPE x, UNION_TYPE y) {
        return root(x) == root(y);
    }
    bool unite(UNION_TYPE x, UNION_TYPE y) {
        x = root(x);y = root(y);
        if (x == y) return false;
        if (siz[x] < siz[y]) swap(x, y);
        par[y] = x;
        siz[x] += siz[y];
        return true;
    }
    UNION_TYPE size(UNION_TYPE x) {
        return siz[root(x)];
    }
};
//mod func の型に注意！！！
//Union Find はUNION_TYPE で型変可能！
//
VI topo_sort(Graph0& G) {
  int N = G.size();
  VI IND(N, 0);
  rep(v, N) {
    arep(nv, G[v]) {
      IND[nv]++;
    }
  }
  queue<int> que;
  rep(v, N) {
    if (IND[v] == 0) {
      que.push(v);
    }
  }
  VI ANS;
  while (!que.empty()) {
    int v = que.front();
    ANS.push_back(v);
    que.pop();
    arep(nv, G[v]) {
      IND[nv]--;
      if (IND[nv] == 0) {
        que.push(nv);
      }
    }
  }
  return ANS;
}
void ADD(int a, int b, Graph0& G) {
  G[a].push_back(b);
  G[b].push_back(a);
}
VP near(int i, int j, int H, int W) {
  VP ans;
  VP cand = {{i - 1, j}, {i + 1, j}, {i, j - 1}, {i, j + 1}};
  arep(v, cand) {
    if (v.first < 0 or v.first >= H) continue;
    if (v.second < 0 or v.second >= W) continue;
    ans.push_back(v);
  }
  return ans;
}
int cast(int i, int j, int H, int W) {
  return ((W * i) + j);
}
ll pows(ll x, ll n, ll mod) {
    if (!n) return 1;
    x %= mod;
    ll r = pows(x, n / 2, mod);
    (r *= r) %= mod;
    if (n % 2) (r *=x) %= mod;
    return r;
}
struct COMB_MOD {
  ll mod;
  int MAX;
  VL fac, finv, inv;
  COMB_MOD(int max, ll m) {
    fac.assign(max, 0);
    finv.assign(max, 0);
    inv.assign(max, 0);
    mod = m;
    MAX = max;
  }
  void solve() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % mod;

        inv[i] = mod - inv[mod%i] * (mod / i) % mod;
        finv[i] = finv[i - 1] * inv[i] % mod;
    }
    
  }
  ll comb(int n, int k) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
  }
};

struct LCA {
    vector<vector<int>> parent;  // parent[k][u]:= u の 2^k 先の親
    vector<int> dist;            // root からの距離
    LCA(const Graph0 &G, int root = 0) { init(G, root); }

    // 初期化
    void init(const Graph0 &G, int root = 0) {
        int V = G.size();
        int K = 1;
        while ((1 << K) < V) K++;
        parent.assign(K, vector<int>(V, -1));
        dist.assign(V, -1);
        dfs(G, root, -1, 0);
        for (int k = 0; k + 1 < K; k++) {
            for (int v = 0; v < V; v++) {
                if (parent[k][v] < 0) {
                    parent[k + 1][v] = -1;
                } else {
                    parent[k + 1][v] = parent[k][parent[k][v]];
                }
            }
        }
    }

    // 根からの距離と1つ先の頂点を求める
    void dfs(const Graph0 &G, int v, int p, int d) {
        parent[0][v] = p;
        dist[v] = d;
        for (auto e : G[v]) {
            if (e != p) dfs(G, e, v, d + 1);
        }
    }

    int query(int u, int v) {
        if (dist[u] < dist[v]) swap(u, v);  // u の方が深いとする
        int K = parent.size();
        // LCA までの距離を同じにする
        for (int k = 0; k < K; k++) {
            if ((dist[u] - dist[v]) >> k & 1) {
                u = parent[k][u];
            }
        }
        // 二分探索で LCA を求める
        if (u == v) return u;
        for (int k = K - 1; k >= 0; k--) {
            if (parent[k][u] != parent[k][v]) {
                u = parent[k][u];
                v = parent[k][v];
            }
        }
        return parent[0][u];
    }
    int get_dist(int u, int v) { return dist[u] + dist[v] - 2 * dist[query(u, v)]; }
};
#include <atcoder/modint>
using namespace atcoder;
using mint = modint998244353;
int main(void) {
    int N, M;cin >> N >> M;
    VI P(N + 1), T(N + 1);
    urep(i, 1, N) {
        int p;cin >> p;
        P[i] = p;
        T[p] = i;
    }
    vector<bool> seen(N + 1, false);
    int K = 0;
    VI R(N + 1);
    VVI CY = {{}};
    urep(s, 1, N) {
        if (seen[s]) continue;
        int now = s;
        K++;
        CY.push_back({});
        while (1) {
            R[now] = s;
            seen[now] = true;
            CY.back().push_back(now);
            int to = P[now];
            if (to == s) break;
            now = to;
        }
    }
    vector<vector<vector<mint>>> dp(N + 1, vector<vector<mint>>(N + 1, vector<mint>(2, 0)));
    int S = 0;
    urep(i, 1, K) {
        S++;
        if (i == 1) {
            dp[S][1][1] = 1;
        } else {
            urep(j, 1, S) {
                dp[S][j][1] = dp[S - 1][j - 1][0] + dp[S - 1][j - 1][1] + ((ll)(j) * (dp[S - 1][j][0] + dp[S - 1][j][1]));
            }
        }
        int m = CY[i].size() - 1;
        urep(l, 1, CY[i].size() - 1) {
            S++;
            urep(j, 1, S) {
                //k = 0
                dp[S][j][0] += dp[S - 1][j - 1][0] + dp[S - 1][j - 1][1];
                //from 0
                dp[S][j][0] += max(j - 2, 0) * dp[S - 1][j][0];
                //from 1
                dp[S][j][0] += (j - 1) * dp[S - 1][j][1];

                //k = 1
                if (l == m) continue;
                //from 0
                dp[S][j][1] = dp[S - 1][j][0];
            }
        }
    }
    mint ans = dp[N][M][0] + dp[N][M][1];
   // cout << S << endl;
    cout << ans.val() << endl;
}

yukicoder

結果

テストケース

ソースコード