結果

問題 No.1978 Permutation Repetition
ユーザー gew1fw
提出日時 2025-06-12 21:35:09
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,086 bytes
コンパイル時間 180 ms
コンパイル使用メモリ 82,224 KB
実行使用メモリ 68,736 KB
最終ジャッジ日時 2025-06-12 21:37:28
合計ジャッジ時間 3,554 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 13 WA * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
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]

    visited = [False] * N
    cycles = []
    for i in range(N):
        if not visited[i]:
            current = i
            cycle = []
            while not visited[current]:
                visited[current] = True
                cycle.append(current)
                current = A[current]
            cycles.append(len(cycle))

    from math import gcd

    # 预计算M的所有因数
    def get_factors(m):
        factors = set()
        for i in range(1, int(m**0.5)+1):
            if m % i == 0:
                factors.add(i)
                factors.add(m // i)
        return sorted(factors)
    factors_M = get_factors(M)

    total = 1
    for k in cycles:
        found = False
        for d in factors_M:
            g = gcd(d, M)
            if k == d // g:
                found = True
                break
        if not found:
            print(0)
            return

    # 计算每个k的可能分解方式数目
    # 特别处理k=1的情况
    from functools import lru_cache

    # 统计所有k=1的数量
    count_k1 = 0
    for k in cycles:
        if k == 1:
            count_k1 += 1

    # 计算f(count_k1)
    @lru_cache(maxsize=None)
    def f(n):
        if n == 0:
            return 1
        if n == 1:
            return 1
        res = f(n-1)
        if n >= 2:
            res += (n-1) * f(n-2)
            res %= MOD
        return res % MOD

    if count_k1 > 0:
        total = (total * f(count_k1)) % MOD

    # 处理其他k的情况
    for k in cycles:
        if k == 1:
            continue
        # 找到所有因数d，使得k = d / gcd(d, M)
        valid = False
        for d in factors_M:
            g = gcd(d, M)
            if k == d // g:
                valid = True
                break
        if not valid:
            print(0)
            return

    print(total % MOD)

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