結果
問題 | No.2428 Returning Shuffle |
ユーザー |
![]() |
提出日時 | 2023-08-25 00:13:38 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 768 ms / 2,000 ms |
コード長 | 892 bytes |
コンパイル時間 | 143 ms |
コンパイル使用メモリ | 82,520 KB |
実行使用メモリ | 265,428 KB |
最終ジャッジ日時 | 2024-12-23 11:54:57 |
合計ジャッジ時間 | 7,302 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
from collections import defaultdictN,M=map(int,input().split())N+=1A=[list(map(int,input().split()))[1:] for _ in range(M)]fact=list(range(N))pset=set()for i in range(2,N):if fact[i]!=i: continuepset.add(i)fact[i]=1for j in range(2*i,N,i):if fact[j]==j:fact[j]//=idef exf(n):res=defaultdict(int)while n>1:res[n//fact[n]]+=1n=fact[n]return resP=list(range(N))Q=list(range(N))for a in A:if len(a)==1: continuefor i in range(len(a)-2,-1,-1):p,q=a[i:i+2]Q[P[p]],Q[P[q]]=Q[P[q]],Q[P[p]]P[p],P[q]=P[q],P[p]seen=[0]*Nstate=defaultdict(int)for i in range(N):if seen[i]: continueif i==Q[i]:seen[i]=1continuect=1p,q=P[i],Q[i]seen[p]=seen[q]=1while p!=i:q=pp=P[p]ct+=1seen[p]=1v=exf(ct)for k in v:state[k]=max(state[k],v[k])MOD=998244353ans=1for k in state:ans*=pow(k,state[k],MOD)ans%=MODprint(ans)