結果

問題 No.896 友達以上恋人未満
ユーザー lam6er
提出日時 2025-04-16 00:33:01
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,397 bytes
コンパイル時間 554 ms
コンパイル使用メモリ 81,332 KB
実行使用メモリ 346,060 KB
最終ジャッジ日時 2025-04-16 00:34:55
合計ジャッジ時間 14,304 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 5 MLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    M, N, mulX, addX, mulY, addY, MOD = map(int, input[ptr:ptr+7])
    ptr +=7
    
    X = list(map(int, input[ptr:ptr+M]))
    ptr += M
    Y = list(map(int, input[ptr:ptr+M]))
    ptr += M
    A = list(map(int, input[ptr:ptr+M]))
    ptr += M
    B = list(map(int, input[ptr:ptr+M]))
    ptr += M
    
    # Initialize z array
    z = [0] * MOD
    # Process first M eels
    for i in range(M):
        x_i = X[i]
        y_i = Y[i]
        z[x_i] += y_i
    
    # Generate eels from M+1 to N
    if N > M:
        x_prev = X[-1] if M > 0 else 0
        y_prev = Y[-1] if M > 0 else 0
        for _ in range(N - M):
            x_i = (x_prev * mulX + addX) % MOD
            y_i = (y_prev * mulY + addY) % MOD
            z[x_i] += y_i
            x_prev = x_i
            y_prev = y_i
    
    # Precompute sum_non_zero
    sum_non_zero = [0] * MOD
    for a in range(1, MOD):
        for x in range(a, MOD, a):
            sum_non_zero[a] += z[x]
    z0 = z[0]
    
    # Process rabbits
    xor_sum = 0
    outputs = []
    
    # First M rabbits
    for j in range(M):
        a_j = A[j]
        b_j = B[j]
        ab = a_j * b_j
        
        if a_j < MOD:
            sum_a = sum_non_zero[a_j] + z0
        else:
            sum_a = z0
        
        if ab < MOD:
            sum_ab = sum_non_zero[ab] + z0
        else:
            sum_ab = z0
        
        ans = sum_a - sum_ab
        outputs.append(ans)
        xor_sum ^= ans
    
    # Rabbits from M+1 to N
    if N > M:
        a_prev = A[-1] if M > 0 else 0
        b_prev = B[-1] if M > 0 else 0
        for j in range(M, N):
            # Compute a_j
            a_j = (a_prev * mulX + addX + MOD - 1) % MOD + 1
            # Compute b_j
            b_j = (b_prev * mulY + addY + MOD - 1) % MOD + 1
            ab = a_j * b_j
            
            if a_j < MOD:
                sum_a = sum_non_zero[a_j] + z0
            else:
                sum_a = z0
            
            if ab < MOD:
                sum_ab = sum_non_zero[ab] + z0
            else:
                sum_ab = z0
            
            ans = sum_a - sum_ab
            xor_sum ^= ans
            
            a_prev = a_j
            b_prev = b_j
    
    # Output
    for ans in outputs:
        print(ans)
    print(xor_sum)

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