‘’’
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.
‘’’
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 question.so 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 .
And[r]=1
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)
