結果

問題 No.1978 Permutation Repetition
ユーザー gew1fw
提出日時 2025-06-12 14:06:26
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,866 bytes
コンパイル時間 238 ms
コンパイル使用メモリ 82,696 KB
実行使用メモリ 77,056 KB
最終ジャッジ日時 2025-06-12 14:06:32
合計ジャッジ時間 4,097 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 15 WA * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from math import gcd
from collections import defaultdict

MOD = 10**9 + 7

def main():
    sys.setrecursionlimit(1 << 25)
    N, M = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    A = [a-1 for a in A]

    # Step 1: Decompose A into cycles and count their lengths
    visited = [False] * N
    cycle_counts = defaultdict(int)
    for i in range(N):
        if not visited[i]:
            cycle_len = 0
            j = i
            while not visited[j]:
                visited[j] = True
                j = A[j]
                cycle_len += 1
            cycle_counts[cycle_len] += 1

    # Step 2: Factorize M and get all divisors
    def get_divisors(m):
        divisors = set()
        for i in range(1, int(m**0.5)+1):
            if m % i == 0:
                divisors.add(i)
                divisors.add(m//i)
        return sorted(divisors)
    divisors = get_divisors(M)

    # Precompute factorial and inverse factorial up to N
    max_n = max(cycle_counts.keys()) if cycle_counts else 0
    max_fact = max(max_n, N)
    fact = [1] * (max_fact + 1)
    for i in range(1, max_fact + 1):
        fact[i] = fact[i-1] * i % MOD
    inv_fact = [1] * (max_fact + 1)
    inv_fact[max_fact] = pow(fact[max_fact], MOD-2, MOD)
    for i in range(max_fact-1, -1, -1):
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD

    # Precompute d_pows for each d and g
    total = 1
    for d, k in cycle_counts.items():
        valid_gs = []
        for g in divisors:
            if (M // g) == 0:
                continue
            if gcd(d, M // g) != 1:
                continue
            valid_gs.append(g)
        # Now compute the generating function's coefficient for x^k
        dp = [0] * (k + 1)
        dp[0] = 1
        for g in valid_gs:
            # Precompute d^g mod MOD
            d_pow_g = pow(d, g, MOD)
            # Precompute 1/g mod MOD
            inv_g = pow(g, MOD-2, MOD)
            # Contribution for each group of size g: (d^g / g) = d^g * inv_g mod MOD
            contrib = d_pow_g * inv_g % MOD
            # Iterate from high to low to avoid overwriting
            for i in range(k, g-1, -1):
                max_m = i // g
                current_contrib = 1
                for m in range(1, max_m + 1):
                    term = contrib * current_contrib % MOD
                    term = term * inv_fact[m] % MOD
                    prev = i - m * g
                    if prev < 0:
                        break
                    dp[i] = (dp[i] + dp[prev] * term) % MOD
                    current_contrib = current_contrib * contrib % MOD
        # The coefficient is dp[k], multiply by k! to get the contribution
        contribution = dp[k] * fact[k] % MOD
        total = total * contribution % MOD
    print(total % MOD)

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