xor
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} |
Timp maxim de executie/ test : 0.2 secunde
stud. Marin Radu
Facultatea de Informatica Iasi
Contact: rss1987@gmail.com