Finding N elements in array whoes xor equals P

Question

I am working on a problem in which I am expected to find the number of combinations of N<20 elements in array whose XOR equals P.

For example: our array is {2 4 5 2 7}

1) if N=2 and P=6,

The answer is 2 (as we can choose only (2 xor 4) = 6 and (4 xor 2) = 6)

{2 4 5 2 7} or {2 4 5 2 7}

2) if N=3 and P=6

The answer is 1 ((4 xor 5 xor 7) = 6)

The size of array can be really huge (something about 10^6) so I am looking for fast algorithm to solve that problem.

Answer 1

EDIT not working because N is fixed

Using linear algebra:

As suggested by @blazs, you can view P and each number of your array as vectors in a Z/2Z vector space. What's more, since XOR is associative and commutative, you're not looking for combinations of elements of your array, but sets of these elements, and a set can also be encoded as a Z/2Z vector.

So you'll end up with a matrix equation like M*S=P, where P is the xor-sum in Z/2Z vector format, M is the matrix which columns are the elements of the array in Z/2Z format , and S is the unknown of the equation.

Since you're only interested in the size of the solution space, all you need to do is find the dimension of the solution space, and then raise 2 to the power of it.