結果

問題 No.2428 Returning Shuffle
ユーザー lloyz
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

from collections import defaultdict
import sys
input = sys.stdin.readline
n, 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 = 998244353
N = set()
seen = set()
for i in range(1, n + 1):
if i in seen:
continue
cnt = 1
seen.add(i)
Stack = [i]
while Stack:
cp = Stack.pop()
np = P[cp]
if np in seen:
continue
seen.add(np)
cnt += 1
Stack.append(np)
N.add(cnt)
ans = 1
PrimeCnt = defaultdict(int)
for num in N:
if num % 2 == 0:
cnt = 0
while num % 2 == 0:
num //= 2
cnt += 1
PrimeCnt[2] = max(PrimeCnt[2], cnt)
f = 3
while f * f <= num:
if num % f == 0:
cnt = 0
while num % f == 0:
num //= f
cnt += 1
PrimeCnt[f] = max(PrimeCnt[f], cnt)
f += 2
if num != 1:
PrimeCnt[num] = max(PrimeCnt[num], 1)
ans = 1
for prime, cnt in PrimeCnt.items():
ans *= pow(prime, cnt, mod)
ans %= mod
print(ans)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0