結果
問題 | No.1392 Don't be together |
ユーザー | 00 Sakuda |
提出日時 | 2024-04-05 01:57:12 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,260 ms / 2,000 ms |
コード長 | 9,889 bytes |
コンパイル時間 | 2,980 ms |
コンパイル使用メモリ | 237,384 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-01 00:45:03 |
合計ジャッジ時間 | 24,498 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 1,224 ms
5,248 KB |
testcase_07 | AC | 1,213 ms
5,248 KB |
testcase_08 | AC | 1,259 ms
5,248 KB |
testcase_09 | AC | 1,260 ms
5,248 KB |
testcase_10 | AC | 1,207 ms
5,248 KB |
testcase_11 | AC | 1,201 ms
5,248 KB |
testcase_12 | AC | 1,209 ms
5,248 KB |
testcase_13 | AC | 1,212 ms
5,248 KB |
testcase_14 | AC | 1,226 ms
5,248 KB |
testcase_15 | AC | 1,208 ms
5,248 KB |
testcase_16 | AC | 1,218 ms
5,248 KB |
testcase_17 | AC | 1,201 ms
5,248 KB |
testcase_18 | AC | 1,223 ms
5,248 KB |
testcase_19 | AC | 1,238 ms
5,248 KB |
testcase_20 | AC | 353 ms
5,248 KB |
testcase_21 | AC | 123 ms
5,248 KB |
testcase_22 | AC | 804 ms
5,248 KB |
testcase_23 | AC | 496 ms
5,248 KB |
testcase_24 | AC | 418 ms
5,248 KB |
testcase_25 | AC | 518 ms
5,248 KB |
testcase_26 | AC | 135 ms
5,248 KB |
testcase_27 | AC | 351 ms
5,248 KB |
testcase_28 | AC | 456 ms
5,248 KB |
testcase_29 | AC | 230 ms
5,248 KB |
ソースコード
#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; vector<vector<mint>> dp(N + 1, vector<mint>(2, 0)); urep(i, 1, K) { S++; vector<vector<mint>> ndp(N + 1, vector<mint>(2, 0)); if (i == 1) { ndp[1][1] = 1; } else { urep(j, 1, S) { ndp[j][1] = dp[j - 1][0] + dp[j - 1][1] + ((ll)(j) * (dp[j][0] + dp[j][1])); } } swap(dp, ndp); int m = CY[i].size() - 1; urep(l, 1, CY[i].size() - 1) { S++; vector<vector<mint>> ndp(N + 1, vector<mint>(2, 0)); urep(j, 1, S) { //k = 0 ndp[j][0] += dp[j - 1][0] + dp[j - 1][1]; //from 0 ndp[j][0] += max(j - 2, 0) * dp[j][0]; //from 1 ndp[j][0] += (j - 1) * dp[j][1]; //k = 1 if (l == m) continue; //from 0 ndp[j][1] = dp[j][0]; } swap(dp, ndp); } } mint ans = dp[M][0] + dp[M][1]; // cout << S << endl; cout << ans.val() << endl; }