Bitmask and Combinatorics

find the number of arrays ar of n non-negative integers where every element is less than 2^k.
and the arrays follow the property:-
a1 & a2 & a3 & . . . & an ≥ a1 ⊕ a2 ⊕ a3 ⊕ . . . ⊕ an.

n is even
Here & denotes the bitwise AND operation, and ⊕ denotes the bitwise XOR operation.

1 Like

it is the codeforces question.recently asked in one of the contest.

this is the solution.

I understood the DP solution, but I wanted to find a pure mathematical expression for it and I found this:-

But there is some problem in this solution.
Its giving correct answer for n=2*(10^5); k=2*(10^5)
but gives wrong answer for n=199992 ; k=2*(10^5)

Can please tell me where I did wrong;

( while deriving the formula I tried using the bits of a1 & a2 & a3…&an )

your approach seems harder for me to get,but the interesting thing is,
you can see i tried the same approach as you did and i missed too many cases i realise after giving too much time to this go through my code and if u face any difficulty in my code,you can ask:)

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)