xor
Да
разгледаме
редица от цели
положителни числа
A1, A2, ..., An.
За подредицата
Ai1, Ai2, ..., Aik (1<=i1<i2<...<ik<= N) дефинираме
xor-сума,
като числото,
получено при
пресмятането
на израза Ai1 xor Ai2 xor ... xor Aik. Подредицата
може да има
нула
елементи (k=0) и в
този случай xor-сумата
е 0.
Задача
Да се определи максималната стойност на xor-сумата, която може да бъде получена от някоя подредица на редицата A, както и броя на подредиците, за които xor-сумата е максимална.
Вход
Файлът xor.in съдържа на първия ред цяло положително число N, представляващо броя на елементите в редицата A. Вторият ред съдържа N цели положителни числа A1 A2 … An, разделени с интервали.
Изход
Файлът xor.out трябва да съдържа два реда. Първият ред трябва да съдържа максималната стойност на xor-сумата, която може да бъде получена от подредица на редицата A. Вторият ред трябва да съдържа цялото положително число Nrsol, представляващо броя на подредиците, за които се достига максимумът на xor-сумата. Тъй като това число може да бъде много голямо, да се изведе само остатъкът при делението на числото Nrsol на 666777.
Ограничения
0 < N <= 5000
0 <= Ai <= 1018
Редицата A се
разглежда
като подредица
на самата
себе си.
Операцията xor представлява
побитово „изключващо
или”. „Изключващо
или” означава:
xor |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
Примери
xor.in |
xor.out |
Обяснение |
xor.in |
xor.out |
Обяснение |
3 |
14 |
Максималната xor-сума е 14. Подредицата с максималната xor-сума е само една {11, 5}. |
5 |
7 |
Максималната xor-сума е 7. Подредиците с максималната xor-сума са: {2,5},{3,4},{1,2,4},{1,3,5} |
Ограничение за време: 0.2 секунди на тест
Студент Marin Radu
Iaşi IT University
За връзка: rss1987@gmail.com
(превод на
български:
Стоян Капралов)