結果

問題 No.2428 Returning Shuffle
ユーザー lam6er
提出日時 2025-03-20 20:38:27
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,550 bytes
コンパイル時間 170 ms
コンパイル使用メモリ 82,512 KB
実行使用メモリ 272,564 KB
最終ジャッジ日時 2025-03-20 20:38:53
合計ジャッジ時間 6,943 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    MOD = 998244353
    input = sys.stdin.read().split()
    ptr = 0
    n, m = int(input[ptr]), int(input[ptr+1])
    ptr += 2

    cycles = []
    for _ in range(m):
        t = int(input[ptr])
        s = list(map(int, input[ptr+1:ptr+1+t]))
        ptr += 1 + t
        cycles.append(s)
    
    # Initialize permutation F as identity
    F = list(range(n + 1))  # 1-based indexing
    
    # Process each cycle in reverse order
    for s in reversed(cycles):
        k = len(s)
        # Create next_s for each element in the cycle
        next_s = [0] * k
        for i in range(k):
            next_s[i] = s[(i+1) % k]
        # Generate the temporary values
        temp = []
        for i in range(k):
            temp.append(F[next_s[i]])
        # Update F for each element in s
        for i in range(k):
            F[s[i]] = temp[i]
    
    # Find the cycle decomposition of F
    visited = [False] * (n + 1)
    lcm = 1
    for i in range(1, n+1):
        if not visited[i]:
            length = 0
            j = i
            while not visited[j]:
                visited[j] = True
                j = F[j]
                length += 1
            # Compute LCM of lcm and length
            def gcd(a, b):
                while b:
                    a, b = b, a % b
                return a
            current_gcd = gcd(lcm, length)
            lcm = (lcm // current_gcd) * length
            lcm %= MOD  # Since LCM can be large, mod by MOD
    
    print(lcm % MOD)

if __name__ == "__main__":
    main()
0