[Help] Divide an array into two subsequences such that the sum of their xor sums is maximum
Difference between en3 and en4, changed 88 character(s)
I'm trying to solve this problem [problem:103708A], in more detail, we need to do this.↵

Given an array $A$ of length $n$ ($n \leq 10^5$, $a_i < 2^{50}$), divide it into two subsequences $X$ and $Y$ such that $(x_1 \oplus ... \oplus x_{|X|}) + (y_1 \oplus ... \oplus y_{|Y|})$ is maximum. Print the maximum $xor\text{_}sum(X) + xor\text{_}sum(Y)$.↵

It is obvious that for each $2^p$, if the ammount of elements $a_i$ such that $a_i \text{ and } 2^p = 2^p$ is odd, the answer will always have its $p$-th bit on. I
f it's even, I'm lost about how to distribute the elements to $X$ and $Y$ or how to get the answer don't know how to handle the case where it's even.↵

Any help would be appreciated. Thanks!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English SuperSheep 2023-01-24 04:58:37 88
en3 English SuperSheep 2023-01-23 21:40:08 13 Tiny change: 'that $a_i & 2^p = 2^p' -> 'that $a_i and 2^p = 2^p' (published)
en2 English SuperSheep 2023-01-23 21:32:25 423 Tiny change: 'x_1 \oplus$' -> 'x_1 \oplus x_2 \oplus ... \oplus x_{|X|}$'
en1 English SuperSheep 2023-01-23 20:56:45 314 Initial revision (saved to drafts)