.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » xp

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
xp


Timp maxim de execuţie / test:
7s
Memorie totala disponibilă / stivă:
4MB / 2MB

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.

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

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[1] B[1] P Q.

Date de ieşire

Fişierul de ieşire xp.out va conţine o singură linie pe care va fi afişată valoarea Rez.

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.

Exemple

xp.inxp.outExplicaţii
5 4 6 10 15 10 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.
3999999 9003 3333 30000 900330000 594979072

autor: Mugurel Ionuţ Andreica
propunător: Prof. Emanuela Cerchez
Liceul de Informatică ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
surse trimise | ajutor