The naive solution is to count all the pairs (i, j) such that A[i] & A[j] = 0 . But of course, it would time out given the constraints. A smarter way is to think in term of bits. The upper bound on the range of numbers is 10^{6}, so, 21 bits would suffice to store any integer in the range, the maximum number that you can represent using 21 bits is 11.....(repeated 21 times), i.e. 1048576, for representation purpose let’s call it MAX. So, we think of every number of the array represented in 21 bits, if some number requires less than 21 bit for representation, we pad rest of the bit after MSB with 0.

Now, for some A[i], A[i] & x = 0 will be satisfied by all those x, where-

- If some bit is set in A[i], then it must be unset in x, otherwise the bitwise & at this bit would be 1 and the overall result of A[i] & x would be non-zero.
- If some bit is unset in A[i] then this bit can be both set and unset in x.

Now, if we flip all the 21 bits of A[i], i.e. turn zeros to one and vice versa, the above twi conditions get reversed, for representation purpose, let’s call ~A[i] as the bit-flipped version of A[i], then.-
- If some bit is set in ~A[i], then this bit can be both unset and set in x.
- If some bit is unset in ~A[i] then this bit must be unset in x.

If you have already worked with bitmasks a bit, then you can realise that we already getting somewhere, every number in the array satisfying the above two conditions can be called as a sub-mask of ~A[i]. But how do, we get ~A[i] from A[i]? It’s easy just XOR A[i] with 11.....(repeated 21 times) i.e. 1048576 or MAX as we denoted it above.

So, the entire task reduces to counting the sum frequency of sub-masks of ~A[i] for every A[i] in the array. And this is where SOS Dynamic Programming Comes into the picture. SOS DP let’s you compute the aggregation of some property over all subsets of a set, and since many sets can share the same subset, we can use DP. All we need is to smartly iterate over the subsets, so, we can form a recurrence relation.

See this tutorial on SOS DP for detail - https://codeforces.com/blog/entry/45223

Here is my accepted solution to the question - https://www.hackerearth.com/submission/35295515/