結果

問題 No.2428 Returning Shuffle
コンテスト
ユーザー miya145592
提出日時 2023-08-18 23:31:12
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,038 ms / 2,000 ms
コード長 2,457 bytes
コンパイル時間 199 ms
コンパイル使用メモリ 82,132 KB
実行使用メモリ 303,536 KB
最終ジャッジ日時 2024-11-28 10:56:16
合計ジャッジ時間 6,809 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

class UnionFind:
    def __init__(self, n, w=None):
        self.par = [-1]*n
        self.rank = [0]*n
        self.siz = [1]*n
        self.cnt = n
        self.min_node = [i for i in range(n)]
        self.weight = w if w else [1]*n

    def root(self, x):
        if self.par[x] == -1:
            return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]

    def issame(self, x, y):
        return self.root(x) == self.root(y)
            
    def unite(self, x, y):
        px = self.root(x)
        py = self.root(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.par[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        self.siz[px] += self.siz[py]
        self.cnt -= 1
        self.min_node[px] = min(self.min_node[px], self.min_node[py])
        self.weight[px] += self.weight[py]
        return False

    def count(self):
        return self.cnt

    def min(self, x):
        return self.min_node[self.root(x)]

    def getweight(self, x):
        return self.weight[self.root(x)]
    
    def size(self, x):
        return self.siz[self.root(x)]

MOD = 998244353
N, M = map(int, input().split())
T = []
S = []
for _ in range(M):
    ts = list(map(int, input().split()))
    T.append(ts[0])
    S.append(ts[1:])
dp = [i for i in range(N)]
for i in range(M):
    bk = dp[S[i][0]-1]
    for j in range(T[i]):
        bk, dp[S[i][(j+1)%T[i]]-1] = dp[S[i][(j+1)%T[i]]-1], bk

seen = [0 for _ in range(N)]
UF = UnionFind(N)
for i in range(N):
    now = i
    if seen[now]:
        continue
    st = i
    seen[now] = 1
    while st!=dp[now]:
        UF.unite(now, dp[now])
        now = dp[now]
        seen[now] = 1
    
import math

d = dict()
for i in range(N):
    r = UF.root(i)
    d[r] = UF.size(r)

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

P = dict()
for key in d:
    f = factorization(d[key])    
    for p, e in f:
        if p not in P:
            P[p] = e
        else:
            P[p] = max(P[p], e)

ans = 1
for p in P:
    ans *= pow(p, P[p], MOD)
    ans %= MOD
print(ans)
0