結果
問題 | No.2531 Coloring Vertices on Namori |
ユーザー |
![]() |
提出日時 | 2023-11-03 22:40:35 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 1,224 ms / 2,000 ms |
コード長 | 1,917 bytes |
コンパイル時間 | 3,022 ms |
コンパイル使用メモリ | 78,628 KB |
実行使用メモリ | 140,048 KB |
最終ジャッジ日時 | 2024-09-25 21:06:13 |
合計ジャッジ時間 | 28,019 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
ソースコード
import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.LinkedHashSet;import java.util.List;public class Main {static int n, k;static List<List<Integer>> list;public static void main(String[] args) throws Exception {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String[] sa = br.readLine().split(" ");n = Integer.parseInt(sa[0]);k = Integer.parseInt(sa[1]);list = new ArrayList<>(n);for (int i = 0; i < n; i++) {list.add(new ArrayList<>());}for (int i = 0; i < n; i++) {sa = br.readLine().split(" ");int u = Integer.parseInt(sa[0]) - 1;int v = Integer.parseInt(sa[1]) - 1;list.get(u).add(v);list.get(v).add(u);}br.close();List<Integer> res = getCycle(0, -1, new LinkedHashSet<>());int size = res.size();int mod = 998244353;long[][] dp = new long[2][size];dp[0][0] = k;for (int i = 1; i < size; i++) {dp[1][i] += dp[0][i - 1] * (k - 1);dp[0][i] += dp[1][i - 1];dp[1][i] += dp[1][i - 1] * (k - 2);dp[1][i] %= mod;}long ans = dp[1][size - 1];ans *= power(k - 1, n - size, mod);ans %= mod;System.out.println(ans);}static List<Integer> getCycle(int x, int p, LinkedHashSet<Integer> his) {if (his.contains(x)) {List<Integer> ret = new ArrayList<>();boolean flg = false;for (int i : his) {if (i == x) {flg = true;}if (flg) {ret.add(i);}}return ret;}his.add(x);for (int i : list.get(x)) {if (i == p) {continue;}List<Integer> res = getCycle(i, x, his);if (res != null) {return res;}}his.remove(x);return null;}static long power(long x, long n, int m) {if (n == 0) {return 1;}long val = power(x, n / 2, m);val = val * val % m;if (n % 2 == 1) {x %= m;val = val * x % m;}return val;}}