結果
問題 | No.2428 Returning Shuffle |
ユーザー |
|
提出日時 | 2023-08-24 21:02:21 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,266 ms / 2,000 ms |
コード長 | 2,913 bytes |
コンパイル時間 | 189 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 335,268 KB |
最終ジャッジ日時 | 2024-12-23 06:57:42 |
合計ジャッジ時間 | 11,786 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
from collections import *from itertools import *from functools import *from heapq import *import sys,mathinput = sys.stdin.readlineN,M = map(int,input().split())class DSU:def __init__(self, n):self._n = nself.parent_or_size = [-1] * ndef merge(self, a, b):assert 0 <= a < self._nassert 0 <= b < self._nx, y = self.leader(a), self.leader(b)if x == y: return xif -self.parent_or_size[x] < -self.parent_or_size[y]: x, y = y, xself.parent_or_size[x] += self.parent_or_size[y]self.parent_or_size[y] = xreturn xdef same(self, a, b):assert 0 <= a < self._nassert 0 <= b < self._nreturn self.leader(a) == self.leader(b)def leader(self, a):assert 0 <= a < self._nif self.parent_or_size[a] < 0: return aself.parent_or_size[a] = self.leader(self.parent_or_size[a])return self.parent_or_size[a]def size(self, a):assert 0 <= a < self._nreturn -self.parent_or_size[self.leader(a)]def groups(self):leader_buf = [self.leader(i) for i in range(self._n)]result = [[] for _ in range(self._n)]for i in range(self._n): result[leader_buf[i]].append(i)return [r for r in result if r != []]class prime_factorize():def __init__(self,M=10**6):self.sieve = [-1]*(M+1)self.sieve[1] = 1self.p = [False]*(M+1)self.mu = [1]*(M+1)for i in range(2,M+1):if self.sieve[i] == -1:self.p[i] = Truei2 = i**2for j in range(i2,M+1,i2):self.mu[j] = 0for j in range(i,M+1,i):self.sieve[j] = iself.mu[j] *= -1def factors(self,x):tmp = []while self.sieve[x] != x:tmp.append(self.sieve[x])x //= self.sieve[x]tmp.append(self.sieve[x])return tmpdef is_prime(self,x):return self.p[x]def mobius(self,x):return self.mu[x]pf = prime_factorize()X = [i for i in range(N)]for _ in range(M):t,*S = map(int,input().split())Y = []for j in range(t):s0 = S[j]-1# s1 = S[(j+1)%t]-1Y.append(X[s0])for j in range(t):s1 = S[(j+1)%t]-1X[s1] = Y[j]# print(X)D = DSU(N)for i,s in enumerate(X):D.merge(i,s)X = [len(g) for g in D.groups()]V = defaultdict(int)for x in X:for k,v in Counter(pf.factors(x)).items():V[k] = max(V[k],v)mod = 998244353ans = 1for k,v in V.items():ans *= pow(k,v,mod)ans %= modprint(ans)