3556 - xorsum

Cerința

Se dau numerele naturale n, x, y, z, t. Se generează vectorul a astfel: a[i] = (a[i-1] * x + y) % z, pentru 1 ≤ i ≤ n si a[i] = 0 pentru i = 0. Determinați ∑(a[i] XOR a[j]), unde 1 ≤ i < j ≤ n, modulo t.

Date de intrare

Programul citește de la tastatură numerele n, x, y, z, t.

Date de ieșire

Programul va afișa pe ecran numărul cerut.

Restricții și precizări

• 1 ≤ n ≤ 250.000
• 1 ≤ x, y, z, t < 2^62

Exemplul 1

Intrare

250001 1 1 4 7

Ieșire

6

Explicație

a = {0, 1, 2, 3}

S = ((1 XOR 2) + (1 XOR 3) + (2 XOR 3)) MOD 7 = (3 + 2 + 1) MOD 7 = 6

Exemplul 2

Intrare

3 1 1 4 7

consola

Datele introduse nu respectă restricțiile.

Rezolvare

def check_restrictions(n, x, y, z, t):
    if not (1 <= n <= 250000):
        print("Eroare: n trebuie să fie între 1 și 250,000.")
        return False
    if not (1 <= x < 2**62 and 1 <= y < 2**62 and 1 <= z < 2**62 and 1 <= t < 2**62):
        print("Eroare: x, y, z, și t trebuie să fie între 1 și 2^62.")
        return False
    return True

def calculate_xor_sum(n, x, y, z, t):
    if not check_restrictions(n, x, y, z, t):
        print("Datele introduse nu respectă restricțiile.")
        return None

    a = [0] * (n + 1)
    xor_sum = 0

    for i in range(1, n + 1):
        a[i] = (a[i - 1] * x + y) % z

    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            xor_sum = (xor_sum + (a[i] ^ a[j])) % t

    return xor_sum

# Citirea datelor de intrare cu mesaje și verificare restricții
input_values = input("Introduceți valorile separate prin spațiu (n x y z t): ").split()

# Verificare dacă numărul de valori introduse este corect
if len(input_values) != 5:
    print("Eroare: Trebuie să introduceți exact 5 valori.")
else:
    n, x, y, z, t = map(int, input_values)
    # Calcularea și afișarea rezultatului
    result = calculate_xor_sum(n, x, y, z, t)
    if result is not None:
        print("Rezultatul este:", result)