結果

問題 No.896 友達以上恋人未満
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 18:48:29
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,647 bytes
コンパイル時間 208 ms
コンパイル使用メモリ 82,160 KB
実行使用メモリ 528,424 KB
最終ジャッジ日時 2025-06-12 18:49:02
合計ジャッジ時間 10,259 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 1 TLE * 2 MLE * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    MOD = 1 << 24  # Just to have it here, actual MOD is read from input
    input = sys.stdin.read().split()
    ptr = 0
    M = int(input[ptr]); ptr +=1
    N = int(input[ptr]); ptr +=1
    mulX = int(input[ptr]); ptr +=1
    addX = int(input[ptr]); ptr +=1
    mulY = int(input[ptr]); ptr +=1
    addY = int(input[ptr]); ptr +=1
    MOD = int(input[ptr]); ptr +=1
    
    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
    
    # Generate x, y, a, b for M+1 to N
    x = [0] * (N + 1)
    y_values = [0] * (N + 1)
    a = [0] * (N + 1)
    b = [0] * (N + 1)
    
    for i in range(1, M+1):
        x[i] = X[i-1] % MOD
        y_values[i] = Y[i-1] % MOD
        a[i] = A[i-1] % MOD
        b[i] = B[i-1] % MOD
    
    for i in range(M+1, N+1):
        x[i] = (x[i-1] * mulX + addX) % MOD
        y_values[i] = (y_values[i-1] * mulY + addY) % MOD
        
        a[i] = (a[i-1] * mulX + addX + MOD -1) % MOD +1
        b[i] = (b[i-1] * mulY + addY + MOD -1) % MOD +1
    
    # Compute z[x]
    z = [0] * MOD
    for i in range(1, N+1):
        xi = x[i] % MOD
        z[xi] += y_values[i]
    
    # Now process each query
    xor_total = 0
    output = []
    
    for j in range(1, M+1):
        aj = a[j]
        bj = b[j]
        ab = aj * bj
        
        sum_a = 0
        for x in range(0, MOD, aj):
            sum_a += z[x]
        
        if ab <= MOD:
            sum_ab = 0
            for x in range(0, MOD, ab):
                sum_ab += z[x]
        else:
            sum_ab = z[0]
        
        Sj = sum_a - sum_ab
        output.append(Sj)
        xor_total ^= Sj
    
    # Process the remaining j from M+1 to N, but in the problem statement, only the first M are output
    # Wait, the problem statement says that for j from M+1 to N, the answer is not output, but the XOR includes all j's.
    # So, for j from M+1 to N, compute Sj and XOR into xor_total.
    
    for j in range(M+1, N+1):
        aj = a[j]
        bj = b[j]
        ab = aj * bj
        
        sum_a = 0
        for x in range(0, MOD, aj):
            sum_a += z[x]
        
        if ab <= MOD:
            sum_ab = 0
            for x in range(0, MOD, ab):
                sum_ab += z[x]
        else:
            sum_ab = z[0]
        
        Sj = sum_a - sum_ab
        xor_total ^= Sj
    
    # Output the first M lines
    for val in output:
        print(val)
    # Output the XOR
    print(xor_total)
    
if __name__ == "__main__":
    main()
0