結果

問題 No.1978 Permutation Repetition
ユーザー chineristACchineristAC
提出日時 2022-06-10 22:58:08
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,360 ms / 2,000 ms
コード長 2,613 bytes
コンパイル時間 277 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 81,968 KB
最終ジャッジ日時 2024-09-21 06:44:55
合計ジャッジ時間 6,335 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 64 ms
68,264 KB
testcase_01 AC 65 ms
68,208 KB
testcase_02 AC 64 ms
68,028 KB
testcase_03 AC 65 ms
68,376 KB
testcase_04 AC 71 ms
72,820 KB
testcase_05 AC 69 ms
70,456 KB
testcase_06 AC 76 ms
72,880 KB
testcase_07 AC 72 ms
71,780 KB
testcase_08 AC 71 ms
72,940 KB
testcase_09 AC 73 ms
72,660 KB
testcase_10 AC 73 ms
73,420 KB
testcase_11 AC 75 ms
72,988 KB
testcase_12 AC 65 ms
69,804 KB
testcase_13 AC 70 ms
70,700 KB
testcase_14 AC 73 ms
74,044 KB
testcase_15 AC 73 ms
73,548 KB
testcase_16 AC 64 ms
68,392 KB
testcase_17 AC 70 ms
72,180 KB
testcase_18 AC 74 ms
73,492 KB
testcase_19 AC 71 ms
73,644 KB
testcase_20 AC 63 ms
69,384 KB
testcase_21 AC 72 ms
71,836 KB
testcase_22 AC 81 ms
72,392 KB
testcase_23 AC 70 ms
71,164 KB
testcase_24 AC 75 ms
72,716 KB
testcase_25 AC 70 ms
71,356 KB
testcase_26 AC 69 ms
71,312 KB
testcase_27 AC 70 ms
72,080 KB
testcase_28 AC 70 ms
71,004 KB
testcase_29 AC 69 ms
71,340 KB
testcase_30 AC 69 ms
71,516 KB
testcase_31 AC 71 ms
72,408 KB
testcase_32 AC 71 ms
72,156 KB
testcase_33 AC 66 ms
68,840 KB
testcase_34 AC 67 ms
68,588 KB
testcase_35 AC 75 ms
71,960 KB
testcase_36 AC 71 ms
71,176 KB
testcase_37 AC 71 ms
72,244 KB
testcase_38 AC 69 ms
70,708 KB
testcase_39 AC 66 ms
68,144 KB
testcase_40 AC 69 ms
69,464 KB
testcase_41 AC 72 ms
71,004 KB
testcase_42 AC 1,360 ms
81,968 KB
testcase_43 AC 281 ms
79,096 KB
testcase_44 AC 65 ms
67,928 KB
testcase_45 AC 65 ms
68,052 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys,random,bisect
from collections import deque,defaultdict
from heapq import heapify,heappop,heappush
from itertools import permutations
from math import log,gcd

input = lambda :sys.stdin.readline().rstrip()
mi = lambda :map(int,input().split())
li = lambda :list(mi())

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    return (g1[n] * g2[r] % mod) * g2[n-r] % mod

mod = 10**9 + 7
N = 2*10**5
g1 = [1]*(N+1)
g2 = [1]*(N+1)
inverse = [1]*(N+1)

for i in range( 2, N + 1 ):
    g1[i]=( ( g1[i-1] * i ) % mod )
    inverse[i]=( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2[i]=( (g2[i-1] * inverse[i]) % mod )
inverse[0]=0

def mul(f,g):
    res = [0 for i in range(len(f)+len(g)-1)]
    for i in range(len(f)):
        for j in range(len(g)):
            res[i+j] += f[i] * g[j] % mod
            res[i+j] %= mod
    return res

def solve(N,M,A):
    if min(A)==1:
        A = [a-1 for a in A]

    visit = [False] * N
    Ls = [0] * (N+1)
    for i in range(N):
        if visit[i]:
            continue
        visit[i] = True
        k = 1
        pos = i
        while not visit[A[pos]]:
            pos = A[pos]
            visit[pos] = True
            k += 1
        Ls[k] += 1
    
    res = 1

    #print(Ls)
    
    for L in range(1,N+1):
        dp = [g1[Ls[L]]]
        for a in range(1,Ls[L]+1):
            if gcd(M,a*L)==a:
                tmp = [0] * (N+1)
                tmp[0] = 1
                p,q = 1,1
                c = pow(L,a-1,mod)
                for k in range(1,N+1):
                    p = (p * c) % mod
                    q = (q * inverse[a]) % mod
                    if a*k <= N:
                        tmp[a*k] = (p*q % mod) * g2[k] % mod
                dp = mul(dp,tmp)[:Ls[L]+1]
        
        #print(L,dp)
        if Ls[L] < len(dp):
            res *= dp[Ls[L]]
        else:
            res = 0
        res %= mod
    
    return res

def brute(N,M,A):
    if min(A)==1:
        A = [a-1 for a in A]
    per = permutations([i for i in range(N)])
    res = 0
    for p in per:
        for i in range(N):
            pos = i
            for _ in range(M):
                pos = p[pos]
                #stack.append(pos)
            if pos!=A[i]:
                break
        else:
            
            #print(p)
            res += 1
    return res

while False:
    N = 8
    M = random.randint(1,10)
    A = [i for i in range(N)]
    random.shuffle(A)
    if solve(N,M,A)!=brute(N,M,A):
        print(N,M)
        print(A)
        print(solve(N,M,A),brute(N,M,A))
        exit()
    


N,M = mi()
A = li()
print(solve(N,M,A))
0