Fişierul intrare/ieşire:	xp.in, xp.out	Sursă	ONI 2010, clasa a 10-a
Autor	Mugurel Ionut Andreica	Adăugată de	Dragos-Alin Rotaru •mathboy
Timp execuţie pe test	0.8 sec	Limită de memorie	5120 kbytes
Scorul tău	N/A	Dificultate	N/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 A₁, B₁ şi o valoare naturală nenulă P, regula după care se calculează elementele şirurilor este următoarea:

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

F mod G reprezintă restul împărţirii lui F la G. Definim Prod_i ca fiind egal cu: (produsul tuturor elementelor şirului val, cu excepţia lui val_i) mod Q. Mai exact, Prod_i = (val₁·val₂·...·val_i-1·val_i+1·...·val_N) 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 = Prod₁ XOR Prod₂ XOR ... XOR Prod_N (adică XOR între toate cele N valori Prod_i, 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, A₁, B₁, 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 ≤ A₁, B₁ ≤ 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

Explicaţie pentru primul exemplu:

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

• A₁=4, B₁=6, val₁=4
• A₂=0, B₂=5, val₂=2
• A₃=5, B₃=5, val₃=5
• A₄=8, B₄=4, val₄=5
• A₅=0, B₅=1, val₅=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.

Cum se trimit solutii?