結果

問題 No.1428 PeRmutation Question
ユーザー lam6er
提出日時 2025-03-20 21:20:04
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,172 bytes
コンパイル時間 278 ms
コンパイル使用メモリ 82,092 KB
実行使用メモリ 89,984 KB
最終ジャッジ日時 2025-03-20 21:21:16
合計ジャッジ時間 3,711 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18 WA * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

def main():
    import sys
    N, *rest = list(map(int, sys.stdin.read().split()))
    P = rest[:N]
    P = [x - 1 for x in P]  # 0-based index

    # Cycle decomposition
    visited = [False] * N
    cycle_counts = {}
    for i in range(N):
        if not visited[i]:
            current = i
            cycle_length = 0
            while not visited[current]:
                visited[current] = True
                cycle_length += 1
                current = P[current]
            cycle_counts[cycle_length] = cycle_counts.get(cycle_length, 0) + 1

    # Precompute factorial and inverse factorial modulo MOD
    max_n = N
    factorial = [1] * (max_n + 1)
    for i in range(1, max_n + 1):
        factorial[i] = factorial[i-1] * i % MOD

    # Compute denominator
    denominator = 1
    for m, k in cycle_counts.items():
        # m^k * k!
        term = pow(m, k, MOD)
        term = term * factorial[k] % MOD
        denominator = denominator * term % MOD

    # Compute inverse of denominator
    inv_denominator = pow(denominator, MOD-2, MOD)
    ans = factorial[N] * inv_denominator % MOD

    print(ans)

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