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

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


Timp maxim de executie/test:
0.2 secunde
Memorie totala disponibila/stiva:
16 MB/1 MB

Se considera sirul de numere naturale A1, A2, ..., An.
Numim suma xor a unui subsir Ai1, Ai2, ..., Aik (1<=i1<i2<...<ik<= N) valoarea obtinuta din evaluarea expresiei Ai1 xor Ai2 xor ... xor Aik. Subsirul poate fi format si din 0 elemente (k=0). Pentru acest caz, suma xor este 0.

Cerinta

Determinati valoarea maxima a sumei xor ce se poate obtine pentru subsirurile sirului A precum si numarul de subsiruri pentru care suma xor este maxima.

Date de intrare

Fisierul xor.in contine pe prima linie numarul natural N reprezentând numarul de elemente din sirul A. Pe cea de-a doua linie se afla cele N valori A1 A2 … An, separate prin cate un spatiu.

Date de iesire

Fisierul xor.out va contine doua linii. Pe prima linie se va afla valoarea maxima posibila a sumei xor ce se poate obtine pentru subsirurile sirului A. Pe cea de-a doua linie se va afla numarul natural Nrsol care reprezinta numarul de subsiruri pentru care se obtine suma xor maxima. Fiindca acest numar poate fi foarte mare, se va afisa doar restul impartitii lui Nrsol la 666777.

Restrictii

0 < N <= 5000
0 <= Ai <= 1018

Sirul A este considerat un subsir al sau.
Operatia xor reprezinta disjunctia exclusiva, efectuata la nivel de biti. Prin disjunctie exclusiva se intelege:

xor
0
1
0
0
1
1
1
0

Exemple

xor.in xor.out Explicatie xor.in xor.out Explicatie
3
11 9 5
14
1
Suma xor maxima este 14. Subsirul cu suma xor maxima este unic si este {11, 5}. 5
1 2 3 4 5
7
4
Suma xor maxima este 7. Cele patru subsiruri cu suma xor maxima sunt: {2,5},{3,4},{1,2,4},{1,3,5}

stud. Marin Radu
Facultatea de Informatica Iasi
Contact: rss1987@gmail.com

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
surse trimise | ajutor