#926119 (C++17) No.2531 Coloring Vertices on Namori

• 問題: No.2531 Coloring Vertices on Namori
• ユーザー: ripity
• 提出日時: 2023-11-03 23:39:41
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 283 ms / 2,000 ms
• コード長: 1,132 bytes
• コンパイル時間: 2,241 ms
• コンパイル使用メモリ: 216,852 KB
• 実行使用メモリ: 61,852 KB
• 最終ジャッジ日時: 2023-11-03 23:39:51
• 合計ジャッジ時間: 8,444 ms
• ジャッジサーバーID （参考情報）: judge13 / judge10

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 4,348 KB
testcase_01	AC	2 ms; 4,348 KB
testcase_02	AC	2 ms; 4,348 KB
testcase_03	AC	2 ms; 4,348 KB
testcase_04	AC	1 ms; 4,348 KB
testcase_05	AC	219 ms; 61,852 KB
testcase_06	AC	1 ms; 4,348 KB
testcase_07	AC	213 ms; 61,852 KB
testcase_08	AC	259 ms; 61,852 KB
testcase_09	AC	283 ms; 61,852 KB
testcase_10	AC	268 ms; 61,852 KB
testcase_11	AC	98 ms; 15,088 KB
testcase_12	AC	98 ms; 15,088 KB
testcase_13	AC	96 ms; 15,088 KB
testcase_14	AC	255 ms; 61,852 KB
testcase_15	AC	256 ms; 61,852 KB
testcase_16	AC	283 ms; 61,852 KB
testcase_17	AC	2 ms; 4,348 KB
testcase_18	AC	2 ms; 4,348 KB
testcase_19	AC	2 ms; 4,348 KB
testcase_20	AC	150 ms; 14,620 KB
testcase_21	AC	148 ms; 14,792 KB
testcase_22	AC	148 ms; 14,620 KB
testcase_23	AC	149 ms; 14,740 KB
testcase_24	AC	146 ms; 14,620 KB
testcase_25	AC	150 ms; 14,620 KB
testcase_26	AC	145 ms; 14,620 KB
testcase_27	AC	147 ms; 14,620 KB
testcase_28	AC	189 ms; 14,620 KB
testcase_29	AC	156 ms; 14,620 KB
testcase_30	AC	183 ms; 14,620 KB
testcase_31	AC	158 ms; 14,884 KB
testcase_32	AC	155 ms; 14,620 KB
testcase_33	AC	162 ms; 14,620 KB

ソースコード

#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;
}