結果

問題 No.896 友達以上恋人未満
ユーザー lam6er
提出日時 2025-03-20 20:39:53
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 4,119 bytes
コンパイル時間 186 ms
コンパイル使用メモリ 82,472 KB
実行使用メモリ 671,964 KB
最終ジャッジ日時 2025-03-20 20:40:19
合計ジャッジ時間 18,578 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 1 MLE * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    MOD_index = 6  # Adjust input reading based on problem's input format

    # Read all input at once
    data = sys.stdin.read().split()
    ptr = 0

    M = int(data[ptr])
    ptr += 1
    N = int(data[ptr])
    ptr += 1
    mulX = int(data[ptr])
    ptr += 1
    addX = int(data[ptr])
    ptr += 1
    mulY = int(data[ptr])
    ptr += 1
    addY = int(data[ptr])
    ptr += 1
    MOD = int(data[ptr])
    ptr += 1

    # Read X
    X = list(map(int, data[ptr:ptr+M]))
    ptr += M
    # Read Y
    Y = list(map(int, data[ptr:ptr+M]))
    ptr += M
    # Read A
    A = list(map(int, data[ptr:ptr+M]))
    ptr += M
    # Read B
    B = list(map(int, data[ptr:ptr+M]))
    ptr += M

    # Initialize z array
    z = [0] * MOD

    # Process first M eels
    for i in range(M):
        xi = X[i] % MOD
        yi = Y[i]
        z[xi] += yi

    # Generate eels for i from M+1 to N
    if M == 0:
        x_prev = 0
        y_prev = 0
        # Since M is 0, first generate from i=1 to N
        for i in range(N):
            xi = (x_prev * mulX + addX) % MOD
            yi = (y_prev * mulY + addY) % MOD
            z[xi] += yi
            x_prev, y_prev = xi, yi
    else:
        x_prev = X[-1]
        y_prev = Y[-1]
        # We have already processed first M eels, now from M+1 to N
        # There are N-M eels to generate
        for _ in range(M, N):
            x_prev = (x_prev * mulX + addX) % MOD
            y_prev = (y_prev * mulY + addY) % MOD
            z[x_prev] += y_prev

    # Build sum_array
    sum_array = [0] * MOD

    # sum_array[0] is unused (d=0 is not considered)
    for d in range(1, MOD):
        total = z[0]  # x=0 is a multiple of any d >=1
        # Add all multiples of d starting from d, then 2d, etc.
        multiple = d
        while multiple < MOD:
            total += z[multiple]
            multiple += d
        sum_array[d] = total

    # Generate a_list and b_list for all N rabbits
    a_list = []
    b_list = []

    # First M rabbits
    for j in range(M):
        a_list.append(A[j])
        b_list.append(B[j])

    # Remaining N-M rabbits
    if M > 0:
        a_prev = A[-1]
        b_prev = B[-1]
    else:
        # If M=0, generate from initial values? Problem's pseudocode may require handling this.
        # For M=0, code uses the pseudocode's initial a and b as zero, then generates first as per code.
        a_prev = (0 * mulX + addX + MOD -1) % MOD +1
        b_prev = (0 * mulY + addY + MOD -1) % MOD +1
        a_list.append(a_prev)
        b_list.append(b_prev)
        # Since M=0 and N can be up to 1e7, handle this case properly
        # But the problem states M <= N, so if M=0, N is >=0, but how to handle generation?
        # For the purpose of this code, assuming that when M=0, we generate from the starting conditions as per pseudocode
        # Which starts with x_prev and y_prev from the first M eels (but M=0) hence initial x_prev and y_prev as per code.

    # Generating from j = M to N-1 (total N-M rabbits)
    for _ in range(M, N):
        a_next = (a_prev * mulX + addX + MOD -1) % MOD + 1
        b_next = (b_prev * mulY + addY + MOD -1) % MOD + 1
        a_list.append(a_next)
        b_list.append(b_next)
        a_prev = a_next
        b_prev = b_next

    # Process each rabbit to compute result
    xor_total = 0
    results = []

    for j in range(N):
        a = a_list[j]
        b = b_list[j]
        d1 = a
        d2 = a * b

        if d1 >= MOD:
            res = 0
        else:
            sum_d1 = sum_array[d1]
            if d2 >= MOD:
                sum_d2 = 0
            else:
                if d2 >= MOD:
                    sum_d2 = 0
                else:
                    sum_d2 = sum_array[d2] if d2 < MOD else 0
            res = sum_d1 - sum_d2
            # Ensure no negative result due to possible 0/0
            res = max(res, 0)
        if j < M:
            results.append(res)
        xor_total ^= res

    # Output first M results
    for res in results:
        print(res)
    # Output XOR total
    print(xor_total)

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