結果
問題 | No.2531 Coloring Vertices on Namori |
ユーザー |
![]() |
提出日時 | 2023-11-03 23:39:41 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 372 ms / 2,000 ms |
コード長 | 1,132 bytes |
コンパイル時間 | 2,231 ms |
コンパイル使用メモリ | 209,204 KB |
最終ジャッジ日時 | 2025-02-17 18:59:03 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
ソースコード
#include <bits/stdc++.h>using namespace std;#include <atcoder/modint>using mint = atcoder::modint998244353;set<int> cycle(vector<vector<int>> &G) {int N = G.size();set<int> ret;vector<int> path;vector<bool> vis_in(N), vis_out(N);auto dfs = [&](auto dfs, int cur, int pre) -> void {path.push_back(cur);vis_in[cur] = true;for( int &nxt : G[cur] ) {if( nxt == pre ) continue;if( !vis_in[nxt] ) {dfs(dfs, nxt, cur);}else if( !vis_out[nxt] ) {int s = find(path.begin(), path.end(), nxt)-path.begin();for( int i = s; i < path.size(); i++ ) ret.insert(path[i]);}}path.pop_back();vis_out[cur] = true;};dfs(dfs, 0, -1);return ret;}int main() {long long N, K;cin >> N >> K;vector<vector<int>> G(N);for( int i = 0; i < N; i++ ) {int u, v;cin >> u >> v;u--, v--;G[u].push_back(v);G[v].push_back(u);}set<int> S = cycle(G);vector<mint> dp(S.size()+1);for( int i = 2; i <= S.size(); i++ ) {dp[i] = K*mint(K-1).pow(i-1)-dp[i-1];}// for( int v : S ) cout << v+1 << endl;cout << (dp[S.size()]*mint(K-1).pow(N-S.size())).val() << endl;}