xor
Consider a
positive integer sequence A1,
A2, ..., An.
We call the xor sum of a subsequence
Ai1, Ai2,
..., Aik (1<=i1<i2<...<ik<=
N) the value obtained by evaluating expression Ai1
xor Ai2 xor ... xor Aik. The subsequence
may be made up of 0 elements
(k=0). For this case, the xor
sum is 0.
Task
Determine the maximum value of the xor sum that can be obtained for the subsequences of sequence A as well as the number of subsequences for which the xor sum is maximal.
Input Data
File xor.in contains on line one positive integer N, representing the number of elements of sequence A. Line two contains N positive integers A1 A2 … An, separated by spaces.
Output Data
File xor.out will contain two lines. The first line will contain the maximum possible value of the xor sum that can be obtained for the subsequences of sequence A. Line two will contain positive integer Nrsol which represents the number of subsequences for which the maximum xor sum is obtained. Because this number can be very large, only the remainder of the division of Nrsol to 666777 will be displayed
Restrictions
0 < N <=
5000
0 <= Ai <= 1018
Sequence A is considered a subsequence
of itself.
The xor
operation represents exclusive disjunction executed at bit level. Exclusive
disjunction means:
|
xor
|
0
|
1
|
|
0
|
0
|
1
|
|
1
|
1
|
0
|
Examples
| xor.in | xor.out | Explanation | xor.in | xor.out | Explanation |
| 3 11 9 5 |
14 1 |
The maximum xor sum is 14. The subsequence with the maximum xor sum is unique and is {11, 5}. | 5 1 2 3 4 5 |
7 4 |
The maximum xor sum is 7. The four subsequences with the maximum xor sum are: {2,5},{3,4},{1,2,4},{1,3,5} |
Time limit: 0.2 seconds/test
student Marin Radu
Iaşi IT University
Contact: rss1987@gmail.com