#1059576 (PyPy3) No.1978 Permutation Repetition

• 問題: 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

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
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()
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX