結果

問題 No.1978 Permutation Repetition
ユーザー lam6er
提出日時 2025-03-26 15:52:42
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 99 ms / 2,000 ms
コード長 2,824 bytes
コンパイル時間 244 ms
コンパイル使用メモリ 81,908 KB
実行使用メモリ 84,496 KB
最終ジャッジ日時 2025-03-26 15:53:13
合計ジャッジ時間 4,442 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math
from collections import defaultdict

MOD = 10**9 + 7

def main():
    N, M = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    A = [a - 1 for a in A]  # 0-based index

    # Precompute combinations and factorials up to 1000
    max_n = 1000
    comb = [[0] * (max_n + 1) for _ in range(max_n + 1)]
    comb[0][0] = 1
    for i in range(1, max_n + 1):
        comb[i][0] = 1
        for j in range(1, i + 1):
            comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % MOD

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

    # Function to get all divisors of M
    def get_divisors(M):
        factors = {}
        temp = M
        i = 2
        while i * i <= temp:
            while temp % i == 0:
                factors[i] = factors.get(i, 0) + 1
                temp //= i
            i += 1
        if temp > 1:
            factors[temp] = 1
        divisors = [1]
        for p in factors:
            exponents = []
            current = 1
            for _ in range(factors[p]):
                current *= p
                exponents.append(current)
            new_divisors = []
            for d in divisors:
                for e in exponents:
                    new_divisors.append(d * e)
            divisors += new_divisors
            divisors = list(set(divisors))
        divisors.sort()
        return divisors

    divisors_M = get_divisors(M)

    # Decompose A into cycles
    visited = [False] * N
    cnt = defaultdict(int)
    for i in range(N):
        if not visited[i]:
            cycle_len = 0
            current = i
            while not visited[current]:
                visited[current] = True
                current = A[current]
                cycle_len += 1
            cnt[cycle_len] += 1

    # Calculate answer
    answer = 1
    for k in cnt:
        c = cnt[k]
        valid_g = []
        for g in divisors_M:
            if M % g != 0:
                continue  # should not happen as divisors_M are divisors of M
            m_over_g = M // g
            if math.gcd(k, m_over_g) == 1:
                valid_g.append(g)
        valid_g.sort()

        dp = [0] * (c + 1)
        dp[0] = 1
        for i in range(1, c + 1):
            for g in valid_g:
                if g > i:
                    continue
                ways = comb[i-1][g-1]
                merge_ways = pow(k, g-1, MOD) * fact[g-1] % MOD
                term = dp[i - g] * ways % MOD
                term = term * merge_ways % MOD
                dp[i] = (dp[i] + term) % MOD
        contribution = dp[c]
        if contribution == 0:
            print(0)
            return
        answer = answer * contribution % MOD

    print(answer % MOD)

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