well, I understood your code. I also came up with this formula when I solved the question first. But I couldn’t guarantee that cases weren’t missing.
So I tried to solve the issue of missing cases by considering all values of And .
Then I got the formula mentioned in picture. The logic isn’t that hard.
I considered an index r in binary representation of And .
Bits of all indices of And on left of index r is 0
and, Bits on indices present on right of r can be anything (because if n= even, then Xor[r] = 0 )
Formula for this is given in above pic.
then I summed r from 1 to k (because there are k possible indices)