結果
問題 | No.2531 Coloring Vertices on Namori |
ユーザー |
![]() |
提出日時 | 2023-11-03 21:43:04 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 144 ms / 2,000 ms |
コード長 | 2,165 bytes |
コンパイル時間 | 7,670 ms |
コンパイル使用メモリ | 351,784 KB |
実行使用メモリ | 17,280 KB |
最終ジャッジ日時 | 2024-09-25 19:47:46 |
合計ジャッジ時間 | 11,030 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
ソースコード
#ifdef DEBUG#define _GLIBCXX_DEBUG#else#pragma GCC target("avx2")#pragma GCC optimize("Ofast,unroll-loops")#endif#include <bits/stdc++.h>#include <atcoder/all>#define rep(i, n) for (int i = 0; i < n; i++)#define per(i, n) for (int i = n - 1; i >= 0; i--)#define ALL(a) a.begin(), a.end()#undef long#define long long longusing namespace std;using mint = atcoder::modint998244353;ostream& operator<<(ostream& os, const mint& a) {return os << a.val();}template<typename T>ostream& operator<<(ostream& os, const vector<T>& a) {const int n = a.size();rep(i, n) os << a[i] << " \n"[i + 1 == n];return os;}template<typename T>istream& operator>>(istream& os, const vector<T>& a) {for (T& i : a) os >> i;return os;}void chmin(int& x, int y) {if (x > y) x = y;}void chmax(int& x, int y) {if (x < y) x = y;}void solve() {constexpr int inf = 1e7;int n, col; cin >> n >> col;atcoder::dsu dsu(n);vector<vector<int>> g(n);int loop = 1;rep(ddd, n) {int u, v; cin >> u >> v; u--, v--;if (dsu.same(u, v)) {vector<int> uu(n, inf);queue<int> q;q.push(u);uu[u] = 0;while (!q.empty()) {const int x = q.front(); q.pop();for (int i : g[x]) {if (uu[i] != inf) continue;uu[i] = uu[x] + 1;q.push(i);}}for (int now = v; now != u;) {for (int i : g[now]) {if (uu[i] + 1 == uu[now]) {now = i;loop++;break;}}}break;}dsu.merge(u, v);g[u].push_back(v);g[v].push_back(u);}vector<mint> fact(n + 1), finv(n + 1);fact[0] = 1;for (int i = 1; i <= n; i++) fact[i] = i * fact[i - 1];finv[n] = fact[n].inv();for (int i = n; i >= 1; i--) finv[i - 1] = i * finv[i];mint ans = 0;for (int i = 0; i <= loop; i++) {const mint comb = finv[i] * finv[loop - i] * fact[loop];const mint mul1 = mint(-1).pow(i);const mint mul2 = mint(col).pow(max(1, loop - i));ans += comb * mul1 * mul2;}ans *= mint(col - 1).pow(n - loop);cout << ans << '\n';}int main() {// srand((unsigned)time(NULL));cin.tie(nullptr);ios::sync_with_stdio(false);cout << fixed << setprecision(40);solve();return 0;}