### SuperSheep's blog

By SuperSheep, history, 18 months ago,

I'm trying to solve this problem 103708A - Anya's gifts, 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 don't know how to handle the case where it's even.

Any help would be appreciated. Thanks!

• +21

 » 18 months ago, # |   0 Auto comment: topic has been updated by SuperSheep (previous revision, new revision, compare).
 » 18 months ago, # |   0 Auto comment: topic has been updated by SuperSheep (previous revision, new revision, compare).
 » 18 months ago, # |   +16
•  » » 18 months ago, # ^ |   +10 Thanks a lot! I was finally able to solve it.
•  » » » 3 weeks ago, # ^ |   0 Could you please give the code or approach for this questions?