結果

問題 No.1978 Permutation Repetition
ユーザー chineristAC
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 44
権限があれば一括ダウンロードができます

ソースコード

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