 # Xor of array

how to count numbers of pairs in array of size n whose xor is equal than x for each value of 0<=x<=k ?
1<=n<=100000
1<=a[i]<=100000000
1<=k<=100000

If it is a question on any site , can you post the link of the question

This is question from Zs contest for placement.

Give some example

I have found a link for you
https://codeforces.com/blog/entry/59579
But I am thinking on an easier solution as well

Are you sure about the value of a[i] ??

Input
3 2
1 2 3
Output
0 1 1
Explanation
N=3 k=2
1^2=3
2^3=1
1^3=2
0 comes 0 times
1 comes 1 times
2 comes 1 times

Yes

Well you can do it like:

• Split the number into groups based on its largest 13 bits, cause they have to be exactly the same.
• Now in each group the numbers are limited at 2 ^ 17. If the group have less than 1000 elements, brute force it. Else, use Walsh Hamadard.

Complexity for Walsh is 2 ^ 17 * 17, and there are at most 100 groups containing more than 1000. The brute force sums up to at most 1000 * 1000 * 100 = 1e8 too.