Fişierul intrare/ieşire:xp.in, xp.outSursăONI 2010, clasa a 10-a
AutorMugurel Ionut AndreicaAdăugată demathboyDragos-Alin Rotaru mathboy
Timp execuţie pe test1.6 secLimită de memorie5120 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Xp

Se consideră 3 şiruri, numite A, B şi val, fiecare dintre ele având câte N elemente naturale nenule. Elementele din cadrul şirurilor sunt indexate de la 1 la N. Cunoscându-se A1, B1 şi o valoare naturală nenulă P, regula după care se calculează elementele şirurilor este următoarea:

  • Pentru 2 ≤ i ≤ N avem:
    • Ai = ((Ai-1 + P - 1) XOR (Bi-1 + 1)) mod P
    • Bi = ((Ai-1 + P - 1) OR (Bi-1 + 1)) mod P.
  • Pentru 1 ≤ i ≤ N avem:
    • vali = max{1, ((i mod P) XOR (((Ai + 1) AND (Bi + 1)) mod P)) mod P}.

F mod G reprezintă restul împărţirii lui F la G. Definim Prodi ca fiind egal cu: (produsul tuturor elementelor şirului val, cu excepţia lui vali) mod Q. Mai exact, Prodi = (val1·val2·...·vali-1·vali+1·...·valN) mod Q. Operaţiile utilizate în formulele de mai sus au următoarea semnificaţie:

  • XOR : sau-exclusiv pe biţi
  • OR : sau pe biţi
  • AND : şi pe biţi

Cerinţă

Să se calculeze valoarea Rez = Prod1 XOR Prod2 XOR ... XOR ProdN (adică XOR între toate cele N valori Prodi, 1 ≤ i ≤ N).

Date de intrare

Fişierul de intrare xp.in conţine pe prima (şi singura) linie 5 numere naturale separate prin câte un spaţiu, reprezentând, în ordine, valorile N, A1, B1, P şi Q.

Date de ieşire

Fişierul de ieşire xp.out va conţine valoarea Rez.

Restricţii

  • 1 ≤ N ≤ 4 000 000
  • 2 ≤ P ≤ 1 000 000 000
  • 2 ≤ Q ≤ 1 000 000 000
  • 0 ≤ A1, B1 ≤ P-1
  • Pentru 30% dintre teste vom avea N ≤ 10 000.
  • Pentru alte 20% dintre teste vom avea 10 001 ≤ N ≤ 200 000.
  • Problema nu urmăreşte găsirea vreunei proprietăţi speciale a relaţiilor de generare a elementelor şirurilor A, B şi val.

Exemplu

xp.inxp.out
5 4 6 10 15
10
3999999 9003 3333 30000 900330000
594979072

Explicaţie pentru primul exemplu:

Se obţin următoarele şiruri A, B şi val:

  • A1=4, B1=6, val1=4
  • A2=0, B2=5, val2=2
  • A3=5, B3=5, val3=5
  • A4=8, B4=4, val4=5
  • A5=0, B5=1, val5=5

Se obţin următoarele valori pentru şirul Prod (în ordine, de la 1 la 5): 10, 5, 5, 5, 5.

Obţinem Rez = 10 XOR 5 XOR 5 XOR 5 XOR 5 = 10.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content