== 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}$
Operaţiile utilizate în formulele de mai sus au următoare semnificaţie:
$XOR$ : sau-exclusiv pe biţi
$OR$ : sau pe biţi
$AND$ : şi pe biţi
$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$.
h2. Cerinta
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
Fişierul de ieşire $xp.out$ va conţine valoarea $Rez$.
În fişierul de ieşire $xp.out$ ...
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.
|
h3. Explicaţie
...
|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$
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") ==
