Binary XOR | CodeChef

Hello dear Problem-Solver,
i solved the Problem BINXOR for small values but still have Problems with larger values.

My Formula for finding the possibilities for one set of bits is:

ElementCount! / CurrentSetBitOnes! * CurrentSetBitZeros!

This Formula works. But:

ElementCount! % mod / (CurrentSetBitOnes! * CurrentSetBitZeros!) % mod

doesn t work.

How do i have to Change the Formula to get correct answers with using mod ?

Check out this - https://www.geeksforgeeks.org/modular-division
It will help.

1 Like

Hey guess what, i also faced the same problem and got wrong answer for the first time i submitted the answer. Then i found out the mistake. So you need to find the modular inverse of the denominator and then multiply with the numerator. This will work!

2 Likes

Modulo like that is only valid for addition, subtraction and multiplication.
For division modulo, you have to use inverse modulo or division modulo that you can find here - https://www.geeksforgeeks.org/modular-division/

1 Like

Thank you !