結果

問題 No.590 Replacement
コンテスト
ユーザー DejianYang
提出日時 2024-11-08 12:57:33
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,155 bytes
コンパイル時間 370 ms
コンパイル使用メモリ 82,340 KB
実行使用メモリ 183,868 KB
最終ジャッジ日時 2024-11-08 12:57:50
合計ジャッジ時間 11,619 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 WA * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import sys
import math

MOD = 10**9 + 7

def extended_gcd(a, b):
    if b == 0:
        return (a, 1, 0)
    else:
        g, y, x = extended_gcd(b, a % b)
        y -= (a // b) * x
        return (g, x, y)

def mod_inverse(a, m):
    g, x, y = extended_gcd(a, m)
    if g !=1:
        return 0
    else:
        return x % m

def main():
    import sys
    import sys
    sys.setrecursionlimit(1 << 25)
    N_and_rest = sys.stdin.read().split()
    N = int(N_and_rest[0])
    A = list(map(int, N_and_rest[1:N+1]))
    B = list(map(int, N_and_rest[N+1: 2*N+1]))
    
    # Find cycles in A
    visited_A = [False]*(N+1)
    cycle_A = {}
    cycle_len_A = {}
    
    pos_in_cycle_A = {}
    for i in range(1, N+1):
        if not visited_A[i]:
            cycle = []
            x = i
            while not visited_A[x]:
                visited_A[x] = True
                cycle.append(x)
                x = A[x-1]
            La = len(cycle)
            for idx, z in enumerate(cycle):
                cycle_A[z] = cycle
                cycle_len_A[z] = La
                pos_in_cycle_A[z] = idx
    
    # Find cycles in B
    visited_B = [False]*(N+1)
    cycle_B = {}
    cycle_len_B = {}
    
    pos_in_cycle_B = {}
    for i in range(1, N+1):
        if not visited_B[i]:
            cycle = []
            x = i
            while not visited_B[x]:
                visited_B[x] = True
                cycle.append(x)
                x = B[x-1]
            Lb = len(cycle)
            for idx, z in enumerate(cycle):
                cycle_B[z] = cycle
                cycle_len_B[z] = Lb
                pos_in_cycle_B[z] = idx
    
    total =0
    for z in range(1, N+1):
        La = cycle_len_A[z]
        Lb = cycle_len_B[z]
        g = math.gcd(La, Lb)
        La_g = La // g
        Lb_g = Lb // g
        inv_La_g = mod_inverse(La_g, Lb_g)
        if Lb_g ==0:
            inv_La_g =0
        # Calculate term1 and term2
        term1 = (La_g * Lb_g * (g -1)) //2
        term2 = (La * inv_La_g * (Lb_g * (Lb_g -1)) ) //2
        total = (total + term1 + term2) % MOD
    print(total)
    
if __name__ == "__main__":
    main()
0