結果

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

ソースコード

diff # 

MOD = 10**9 + 7

def main():
    import sys
    sys.setrecursionlimit(1 << 25)
    N = int(sys.stdin.readline())
    P = list(map(int, sys.stdin.readline().split()))
    P = [p - 1 for p in P]  # 0-based index

    # Precompute factorial and inverse factorial modulo MOD
    max_n = 10**5 + 10
    fact = [1] * (max_n)
    for i in range(1, max_n):
        fact[i] = fact[i-1] * i % MOD
    inv_fact = [1] * (max_n)
    inv_fact[max_n-1] = pow(fact[max_n-1], MOD-2, MOD)
    for i in range(max_n-2, -1, -1):
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD

    # Find cycles in P
    visited = [False] * N
    cycles = []
    for i in range(N):
        if not visited[i]:
            current = i
            cycle = []
            while not visited[current]:
                visited[current] = True
                cycle.append(current)
                current = P[current]
            cycles.append(len(cycle))

    # Check if all cycles are odd and each cycle length occurs exactly once
    from collections import defaultdict
    cycle_counts = defaultdict(int)
    for c in cycles:
        cycle_counts[c] += 1
    all_odd = all(c % 2 == 1 for c in cycles)
    all_distinct = all(cnt == 1 for cnt in cycle_counts.values())

    # Compute denominator
    denominator = 1
    for c in cycle_counts:
        m = cycle_counts[c]
        denominator = denominator * pow(c, m, MOD) % MOD
        denominator = denominator * fact[m] % MOD

    # Compute conjugacy class size
    if N == 0:
        conj_size = 0
    else:
        conj_size = fact[N] * pow(denominator, MOD-2, MOD) % MOD

    # Determine answer
    if all_odd and all_distinct:
        if N == 1:
            print(1 % MOD)
        else:
            inv2 = pow(2, MOD-2, MOD)
            ans = conj_size * inv2 % MOD
            print(ans)
    else:
        print(conj_size % MOD)

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