結果
問題 | No.2531 Coloring Vertices on Namori |
ユーザー | chineristAC |
提出日時 | 2023-11-03 21:52:36 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 454 ms / 2,000 ms |
コード長 | 1,153 bytes |
コンパイル時間 | 270 ms |
コンパイル使用メモリ | 81,868 KB |
実行使用メモリ | 166,268 KB |
最終ジャッジ日時 | 2023-11-03 21:52:49 |
合計ジャッジ時間 | 11,404 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 53 ms
67,012 KB |
testcase_01 | AC | 52 ms
67,012 KB |
testcase_02 | AC | 53 ms
67,012 KB |
testcase_03 | AC | 53 ms
67,012 KB |
testcase_04 | AC | 52 ms
67,012 KB |
testcase_05 | AC | 252 ms
137,712 KB |
testcase_06 | AC | 54 ms
67,012 KB |
testcase_07 | AC | 253 ms
137,712 KB |
testcase_08 | AC | 389 ms
138,840 KB |
testcase_09 | AC | 403 ms
138,852 KB |
testcase_10 | AC | 376 ms
138,856 KB |
testcase_11 | AC | 221 ms
166,268 KB |
testcase_12 | AC | 221 ms
166,268 KB |
testcase_13 | AC | 223 ms
166,268 KB |
testcase_14 | AC | 325 ms
137,504 KB |
testcase_15 | AC | 337 ms
137,508 KB |
testcase_16 | AC | 327 ms
137,492 KB |
testcase_17 | AC | 52 ms
67,012 KB |
testcase_18 | AC | 51 ms
67,012 KB |
testcase_19 | AC | 51 ms
67,012 KB |
testcase_20 | AC | 411 ms
141,572 KB |
testcase_21 | AC | 454 ms
141,584 KB |
testcase_22 | AC | 392 ms
141,580 KB |
testcase_23 | AC | 397 ms
141,588 KB |
testcase_24 | AC | 408 ms
141,580 KB |
testcase_25 | AC | 383 ms
141,580 KB |
testcase_26 | AC | 379 ms
141,584 KB |
testcase_27 | AC | 412 ms
141,576 KB |
testcase_28 | AC | 359 ms
141,580 KB |
testcase_29 | AC | 357 ms
141,600 KB |
testcase_30 | AC | 384 ms
141,584 KB |
testcase_31 | AC | 407 ms
141,620 KB |
testcase_32 | AC | 375 ms
141,604 KB |
testcase_33 | AC | 375 ms
141,568 KB |
ソースコード
import sys from itertools import permutations from heapq import heappop,heappush from collections import deque import random import bisect input = lambda :sys.stdin.readline().rstrip() mi = lambda :map(int,input().split()) li = lambda :list(mi()) def cmb(n, r, mod): if ( r<0 or r>n ): return 0 return (g1[n] * g2[r] % mod) * g2[n-r] % mod mod = 998244353 N = 2*10**5 g1 = [1]*(N+1) g2 = [1]*(N+1) inverse = [1]*(N+1) for i in range( 2, N + 1 ): g1[i]=( ( g1[i-1] * i ) % mod ) inverse[i]=( ( -inverse[mod % i] * (mod//i) ) % mod ) g2[i]=( (g2[i-1] * inverse[i]) % mod ) inverse[0]=0 N,K = mi() edge = [set() for v in range(N)] for _ in range(N): u,v = mi() edge[u-1].add(v-1) edge[v-1].add(u-1) deq = deque([v for v in range(N) if len(edge[v]) == 1]) rest = N while deq: v = deq.popleft() pv = edge[v].pop() edge[pv].remove(v) rest -= 1 if len(edge[pv]) == 1: deq.append(pv) dp = [0] * (rest+1) dp[1] = K dp[2] = K * (K-1) for n in range(3,rest+1): dp[n] = K * pow(K-1,n-1,mod) - dp[n-1] dp[n] %= mod res = dp[rest] * pow(K-1,N-rest,mod) % mod print(res) #print(dp)