結果
問題 | No.2428 Returning Shuffle |
ユーザー |
![]() |
提出日時 | 2023-08-18 21:50:57 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 759 ms / 2,000 ms |
コード長 | 1,229 bytes |
コンパイル時間 | 255 ms |
コンパイル使用メモリ | 81,996 KB |
実行使用メモリ | 268,692 KB |
最終ジャッジ日時 | 2024-11-28 06:37:26 |
合計ジャッジ時間 | 6,715 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
from collections import defaultdictimport sysinput = sys.stdin.readlinedef prime_factor(n):factors = {}if n % 2 == 0:cnt = 0while n % 2 == 0:cnt += 1n //= 2factors[2] = cnti = 3while i * i <= n:if n % i == 0:cnt = 0while n % i == 0:cnt += 1n //= ifactors[i] = cnti += 2if n != 1:factors[n] = 1return factorsmod = 998244353N, M = map(int, input().split())P = list(range(N))Q = list(range(N))for _ in range(M):T, *S = map(int, input().split())S = list(map(lambda x: x-1, S))tmp = Q[P[S[0]]]x = [P[S[0]]]for i in range(T-1):Q[P[S[i]]] = Q[P[S[i+1]]]x.append(P[S[i+1]])Q[P[S[T-1]]] = tmpfor i in x:P[Q[i]] = ivisited = [0] * Nexp = defaultdict(int)for i in P:if visited[i]:continuej = P[i]cnt = 1visited[j] = 1while j != i:j = P[j]cnt += 1visited[j] = 1for p, c in prime_factor(cnt).items():exp[p] = max(exp[p], c)ans = 1for p, e in exp.items():ans = ans * pow(p, e, mod) % modprint(ans)