結果
問題 | No.2428 Returning Shuffle |
ユーザー |
|
提出日時 | 2023-08-19 14:46:10 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 748 ms / 2,000 ms |
コード長 | 1,258 bytes |
コンパイル時間 | 321 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 286,388 KB |
最終ジャッジ日時 | 2024-11-29 08:10:52 |
合計ジャッジ時間 | 7,302 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
from collections import defaultdictimport sysinput = sys.stdin.readlinen, m = map(int, input().split())P = [i for i in range(n + 1)]for _ in range(m):t, *S = map(int, input().split())sigma = []for i in range(t):sigma.append(P[S[i]])for i in range(t):j = S[(i + 1) % t]P[j] = sigma[i]mod = 998244353N = set()seen = set()for i in range(1, n + 1):if i in seen:continuecnt = 1seen.add(i)Stack = [i]while Stack:cp = Stack.pop()np = P[cp]if np in seen:continueseen.add(np)cnt += 1Stack.append(np)N.add(cnt)ans = 1PrimeCnt = defaultdict(int)for num in N:if num % 2 == 0:cnt = 0while num % 2 == 0:num //= 2cnt += 1PrimeCnt[2] = max(PrimeCnt[2], cnt)f = 3while f * f <= num:if num % f == 0:cnt = 0while num % f == 0:num //= fcnt += 1PrimeCnt[f] = max(PrimeCnt[f], cnt)f += 2if num != 1:PrimeCnt[num] = max(PrimeCnt[num], 1)ans = 1for prime, cnt in PrimeCnt.items():ans *= pow(prime, cnt, mod)ans %= modprint(ans)