結果

問題 No.590 Replacement
ユーザー DejianYangDejianYang
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 40 ms
52,224 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 AC 40 ms
52,608 KB
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 WA -
testcase_42 WA -
testcase_43 WA -
testcase_44 AC 218 ms
170,628 KB
testcase_45 WA -
testcase_46 WA -
権限があれば一括ダウンロードができます

ソースコード

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