結果

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

ソースコード

diff # 

MOD = 10**9 + 7

def main():
    import sys
    sys.setrecursionlimit(1 << 25)
    N, *rest = list(map(int, sys.stdin.read().split()))
    P = rest[:N]

    visited = [False] * (N + 1)  # 1-based
    cycle_counts = {}

    for i in range(1, N + 1):
        if not visited[i]:
            length = 0
            j = i
            while not visited[j]:
                visited[j] = True
                j = P[j-1]
                length += 1
            cycle_counts[length] = cycle_counts.get(length, 0) + 1

    max_n = N
    fact = [1] * (max_n + 1)
    for i in range(1, max_n + 1):
        fact[i] = fact[i-1] * i % MOD

    inv_fact = [1] * (max_n + 1)
    inv_fact[max_n] = pow(fact[max_n], MOD-2, MOD)
    for i in range(max_n-1, -1, -1):
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD

    denominator = 1
    for l, cnt in cycle_counts.items():
        term = pow(l, cnt, MOD)
        term = term * fact[cnt] % MOD
        denominator = denominator * term % MOD

    numerator = fact[N]
    inv_denominator = pow(denominator, MOD-2, MOD)
    answer = numerator * inv_denominator % MOD
    print(answer)

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