結果
問題 | No.2428 Returning Shuffle |
ユーザー |
|
提出日時 | 2023-08-19 09:46:52 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 778 ms / 2,000 ms |
コード長 | 1,369 bytes |
コンパイル時間 | 220 ms |
コンパイル使用メモリ | 82,444 KB |
実行使用メモリ | 266,520 KB |
最終ジャッジ日時 | 2024-11-29 01:09:47 |
合計ジャッジ時間 | 6,866 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
def Multiple_LCM(A: list) -> int:'''複数の整数に対する最小公倍数を返すParameters----------A:list'''from collections import defaultdictMOD = 998244353Exponent = defaultdict(int)for a in A:primes = []for i in range(2, a+1):if i*i > a:breakif a % i != 0:continuecnt = 0while a % i == 0:cnt += 1a //= iprimes.append((i, cnt))if a > 1:primes.append((a, 1))for p, v in primes:Exponent[p] = max(Exponent[p], v)res = 1for p, exp in Exponent.items():res *= pow(p, exp, MOD)res %= MODreturn resN, M = map(int, input().split())P = [i for i in range(N)]for _ in range(M):L, *T = list(map(int, input().split()))sigma = []for t in T:sigma.append(P[t-1])for i in range(L):if i < L-1:j = T[i+1]-1else:j = T[0]-1P[j] = sigma[i]loop = []seen = [False]*Nfor i in range(N):if seen[i]:continuetmp = 1seen[i] = Truenext = P[i]while not seen[next]:seen[next] = Truetmp += 1next = P[next]loop.append(tmp)ans = Multiple_LCM(loop)print(ans)