結果

問題 No.896 友達以上恋人未満
ユーザー lam6er
提出日時 2025-03-31 17:53:02
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,196 bytes
コンパイル時間 168 ms
コンパイル使用メモリ 82,832 KB
実行使用メモリ 502,392 KB
最終ジャッジ日時 2025-03-31 17:54:16
合計ジャッジ時間 16,134 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 1 MLE * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    M = int(input[idx]); idx +=1
    N = int(input[idx]); idx +=1
    mulX = int(input[idx]); idx +=1
    addX = int(input[idx]); idx +=1
    mulY = int(input[idx]); idx +=1
    addY = int(input[idx]); idx +=1
    MOD = int(input[idx]); idx +=1

    X = list(map(int, input[idx:idx+M]))
    idx += M
    Y = list(map(int, input[idx:idx+M]))
    idx += M
    A = list(map(int, input[idx:idx+M]))
    idx += M
    B = list(map(int, input[idx:idx+M]))
    idx += M

    # Generate a and b arrays
    a = [0] * (N + 1)
    b = [0] * (N + 1)
    for i in range(1, M+1):
        a[i] = A[i-1]
        b[i] = B[i-1]
    
    for i in range(M+1, N+1):
        prev_a = a[i-1]
        new_a = (prev_a * mulX + addX + MOD -1) % MOD + 1
        a[i] = new_a
        
        prev_b = b[i-1]
        new_b = (prev_b * mulY + addY + MOD -1) % MOD + 1
        b[i] = new_b

    # Initialize z array
    z = [0] * MOD
    if M > 0:
        x_prev = X[0]
        y_prev = Y[0]
        z[x_prev] += y_prev
        for j in range(1, M):
            x_prev = X[j]
            y_prev = Y[j]
            z[x_prev] += y_prev
    
    # Generate remaining x and y and accumulate into z
    for j in range(M+1, N+1):
        x_prev = (x_prev * mulX + addX) % MOD
        y_prev = (y_prev * mulY + addY) % MOD
        z[x_prev] += y_prev

    # Compute sum_multiples
    sum_multiples = [0] * (MOD + 2)  # 1-based to MOD

    for d in range(1, MOD+1):
        total = 0
        multiple = 0
        while multiple < MOD:
            total += z[multiple]
            multiple += d
        sum_multiples[d] = total

    # Process each rabbit
    first_ans = []
    xor_total = 0
    for j in range(1, N+1):
        d1 = a[j]
        d2 = a[j] * b[j]
        if d1 > MOD:
            s1 = 0
        else:
            s1 = sum_multiples[d1]
        if d2 <= MOD:
            s2 = sum_multiples[d2]
        else:
            s2 = 0
        ans = s1 - s2
        if j <= M:
            first_ans.append(ans)
        xor_total ^= ans

    # Output
    for ans in first_ans:
        print(ans)
    print(xor_total)

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