# Find xor sum of all pairs raised to power of 3

We are given array $$A$$ of $$N$$ integers each in the range $$1 \leq A_i \leq 2^{30}$$, that is we can write each integer with at most 30 bits. The target is to compute $$\sum_{1\leq i \leq N,1\leq j. $$X$$ is either 2 or 3. $$N$$ can be up to $$50000$$.

I know that this can be solved in $$O(N^2)$$ but I was wondering if we can fast this calculation since this is pretty slow for big values of $$N$$. Are there any properties of xor that can be used to speed up calculations.

• Is $X$ the same for all terms $(A_i\ \mathrm{xor}\ A_j)^X$? – xskxzr Dec 2 at 4:30
• Yes, x is same for all pairs – someone12321 Dec 2 at 6:49