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

<syntaxhighlight lang="python3"> 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

1. 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()

1. 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)

</syntaxhighlight>