xp

Xp

== include(page="template/taskheader" task_id="xp") ==

Poveste şi cerinţă...

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{~1~}$, $B{~1~}$ ş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{~1~}·val{~2~}·...·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
 
h2. Cerinţă
 
Să se calculeze valoarea $Rez = Prod{~1~} XOR Prod{~2~} XOR ... XOR Prod{~N~}$ (adică $XOR$ între toate cele $N$ valori $Prod{~i~}, 1 ≤ i ≤ N$).

h2. Date de intrare

Fişierul de intrare $xp.in$ ...

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{~1~}, B{~1~}$, $P$ şi $Q$.

h2. Date de ieşire

În fişierul de ieşire $xp.out$ ...

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

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 4 000 000$
* $2 ≤ P ≤ 1 000 000 000$
* $2 ≤ Q ≤ 1 000 000 000$
* $0 ≤ A{~1~}, B{~1~} ≤ 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$.

h2. Exemplu
table(example). |_. xp.in |_. xp.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

|5 4 6 10 15
|10
|
table(example).
|3999999 9003 3333 30000 900330000
|594979072
|
 
h3. Explicaţie pentru primul exemplu:
 
Se obţin următoarele şiruri $A$, $B$ şi $val$:
 
* $A{~1~}=4, B{~1~}=6, val{~1~}=4$
* $A{~2~}=0, B{~2~}=5, val{~2~}=2$
* $A{~3~}=5, B{~3~}=5, val{~3~}=5$
* $A{~4~}=8, B{~4~}=4, val{~4~}=5$
* $A{~5~}=0, B{~5~}=1, val{~5~}=5$

h3. Explicaţie

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$.

== include(page="template/taskfooter" task_id="xp") ==

4750