結果
問題 | No.2531 Coloring Vertices on Namori |
ユーザー |
|
提出日時 | 2023-11-03 22:56:54 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 167 ms / 2,000 ms |
コード長 | 2,742 bytes |
コンパイル時間 | 3,785 ms |
コンパイル使用メモリ | 266,812 KB |
最終ジャッジ日時 | 2025-02-17 18:45:00 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
ソースコード
#ifdef ONLINE_JUDGE #include <bits/stdc++.h> #include <atcoder/all> #else #include <mylibs/all.h> #endif using ll = long long; using lll = __int128_t; #define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i) #define reps(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i) #define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; --i) #define rreps(i, n) for (int i = ((int)(n)); i > 0; --i) #define rep2(i, s, n) for (int i = (s); i < (int)(n); i++) #define repc2(i, s, n) for (int i = (s); i <= (int)(n); i++) #define length(v) ((int)(v).size()) constexpr int inf = 2'000'000'000; constexpr ll linf = 4'000'000'000'000'000'000, M7 = 1'000'000'007, M9 = 998'244'353; #define all(v) begin(v), end(v) #define rall(v) rbegin(v), rend(v) using namespace std; using namespace atcoder; using mint = modint998244353; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, k; cin >> n >> k; struct edge { int to; edge(int to) : to(to) {} }; vector<vector<edge>> G(n); rep(i, n) { int a, b; cin >> a >> b; a--, b--; G[a].emplace_back(b); G[b].emplace_back(a); } auto search_cycle = [](const auto& G) { const int n = G.size(); vector<bool> seen(n); vector<int> prv(n, -1); rep(i, n) { if (seen.at(i)) continue; stack<int> s; s.emplace(i); while (!s.empty()) { int u = s.top(); s.pop(); seen.at(u) = true; for (auto& e : G.at(u)) { if (!seen.at(e.to)) { prv.at(e.to) = u; s.emplace(e.to); } else if (e.to != prv.at(u)) { vector<int> cycle = {u}; int p = u; while (p != e.to) { p = prv.at(p); cycle.emplace_back(p); } reverse(all(cycle)); return cycle; } } } } return vector<int>(); }; auto cycle = search_cycle(G); set<int> st(all(cycle)); int m = cycle.size(); vector<vector<mint>> dp = vector<vector<mint>>(m, vector<mint>(2)); dp.at(0).at(1) = k; rep(i, m - 2) { dp.at(i + 1).at(0) = dp.at(i).at(0) * (k - 2) + dp.at(i).at(1) * (k - 1); dp.at(i + 1).at(1) = dp.at(i).at(0); } dp.at(m - 1).at(0) = dp.at(m - 2).at(0) * (k - 2) + dp.at(m - 2).at(1) * (k - 1); mint ans = dp.at(m - 1).at(0) * mint(k - 1).pow(n - cycle.size()); cout << ans.val() << endl; return 0; }