First of all, suppose that we have fixed values of x which we will use for xoring. Then, for A_i we can change it to any A_i \oplus y, such that y belongs to linear span of x.
It means, that we can consider only some choises of x which represent linear span(and which will be easier for us to track).
We will consider staircase(not sure if it’s common name) basis – for any x_i in basis, it’s leading bit is not present in any other x_j in basis(i.e., if 2^k \le x_i < 2^{k+1}, for any j \ne i x_j doesn’t contain k-th bit). If you will write this numbers in decreasing order, it will look like staircase.
For this kind of basis, it’s actually easy to find which numbers we will xor with A_i(after fixing numbers in basis):
Since largest bit of number is present only in one number, we can go in decreasing order of numbers, and xor A_i with x, if it doesn’t contain largest bit of x.
So, we already can solve problem in some nontrivial way – suppose that we have fixed largest bits of numbers that we will choose(but didn’t choose all other bits). Then, for each A_i, we already know which numbers x will be xored with it. It means that for each bit, that is not largest for any of x, we can proceed independently. There are some nontrivial ways to solve it(which work slower for such small values of k), but we can just proceed naively – just iterate over all 2^k values to set this bit in each of x, take max over all choices, do this for each non-largest bit separately, sum up answers.
This solution works in O(C(m, k)nm2^k), where C(m, k) denotes binomial coefficient. It allows us to solve subtasks with k \le 3. For bigger k we need to speed up somehow.
Let’s do similar solution, but in recursive way. We will go in decreasing order of bits, maintaing how many numbers we already chosen.
For each bit we have two options:
- If we used less than k numbers we can create new number x which will have largest bit equal to this.
- Not use this number for the largest bit – calculate maximum answer for this bit in the same way as above(iterating over all 2^{chosen} choices).
(In previous solution, we tried both options).
To optimize it, let’s firstly calculate answer with 2. If we’ve found, that max answer is n, then it’s make no sense to go with option 1.
Other optimize is the following – suppose that we know largest bit(let’s name it bt), where option 2 didn’t produce answer n, then we will need to go with option 1 in bit not less then bt - log(n).
Why it’s true, if we go with option 1, then we are able to produce answer at least 2^bt and if we don’t use option 2 for all bits not smaller than bt - log(n) then our answer will be not bigger then n(2^{bt - log(n)} - 1) = 2^{bt}.
This means that every log(n) bits where answer found using 2 is not equal to n we need to use option 1. Then, our solution works in O(log(n)^k2^knm).
Another way, to implement this optimize is to store current answer and best answer and don’t proceed further if currentanswer + (2^{bt + 1} - 1)n \le bestanswer.