結果

問題 No.1428 PeRmutation Question
ユーザー lam6er
提出日時 2025-04-15 23:00:39
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 64 ms / 2,000 ms
コード長 1,917 bytes
コンパイル時間 176 ms
コンパイル使用メモリ 81,788 KB
実行使用メモリ 90,276 KB
最終ジャッジ日時 2025-04-15 23:01:30
合計ジャッジ時間 2,854 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

def main():
    import sys
    input = sys.stdin.read().split()
    N = int(input[0])
    P = list(map(int, input[1:N+1]))
    
    # Compute cycle decomposition
    visited = [False] * (N + 1)  # 1-based
    cycle_counts = {}
    for i in range(1, N+1):
        if not visited[i]:
            current = i
            cycle = []
            while not visited[current]:
                visited[current] = True
                cycle.append(current)
                current = P[current - 1]  # P is 1-based
            cycle_len = len(cycle)
            if cycle_len in cycle_counts:
                cycle_counts[cycle_len] += 1
            else:
                cycle_counts[cycle_len] = 1
    
    # Check if all cycles are of length 1 (identity permutation)
    if all(d == 1 for d in cycle_counts.keys()):
        print(1)
        return
    
    # Check conditions for centralizer having elements of odd parity
    has_even = any(d % 2 == 0 for d in cycle_counts)
    has_odd_multiple = any(d % 2 == 1 and cnt >= 2 for d, cnt in cycle_counts.items())
    if has_even or has_odd_multiple:
        compute_conjugacy = True
    else:
        compute_conjugacy = False
    
    # Precompute factorial and inverse factorial modulo MOD
    max_n = N
    fact = [1] * (max_n + 1)
    for i in range(1, max_n + 1):
        fact[i] = fact[i-1] * i % MOD
    
    # Compute denominator
    denominator = 1
    for d, cnt in cycle_counts.items():
        term_d = pow(d, cnt, MOD)
        term_fact = fact[cnt]
        denominator = denominator * term_d % MOD
        denominator = denominator * term_fact % MOD
    
    # Compute conjugacy class size
    conj_size = fact[N] * pow(denominator, MOD-2, MOD) % MOD
    
    if compute_conjugacy:
        print(conj_size)
    else:
        inv_2 = pow(2, MOD-2, MOD)
        res = conj_size * inv_2 % MOD
        print(res)

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