## Editorial for GlobeX Cup '18 S3 - Playing With Bits

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Ninjaclasher

For the first subtask, we can brute force all possible combinations of the array , and check if they match the constraints.

Time Complexity: For the rest of the subtasks (in general), we need to improve the time complexity.

Let us look at the xor operation first. A bit in is set if and only if there is an odd number of s with the bit set. A bit in is not set if there is an even number of s with the bit set. Thus, we need to look at each bit in individually. If the bit is set, we need to calculate the number of ways to place an odd number of set bits in the array of size . Thus, ( choose an odd number). If the bit is not set, we need to calculate the number of ways to place an even number of set bits in the array of size . Thus, ( choose an even number).

For the or operation, the bit in is set if any of has set bit . An bit in is unset if all of has an unset bit . Similar to the xor operation, we must loop through each bit. There are ways to choose a combination for the elements, such that at least one of them has a set bit , and there is exactly way to choose a combination for the elements, such that all bit s are unset.

The and operation can be handled in the same manner as the or operation, and so we will leave it as an exercise for the reader.

With this, we can go through each bit up to , and multiply the number of ways for each bit accordingly. Be wary to modulo to prevent overflow.

It is trivial to calculate with Exponentiation By Squaring. To calculate and quickly requires a little more mathematical insight (which are the next 3 subtasks).

For the second subtask, we can precompute by looping up to ( to inclusive), and calculate . Multiply all even into a final variable, and all odd into another variable. Note that we need to use modular division in order to prevent overflow. Noticing that is a prime, we can use Fermat's Little Theorem to calculate the modular multiplicative inverse, and perform modular division accordingly (by multiplying by the modular multiplicative inverse).

Time Complexity: For the third subtask, we notice that is not a prime. Instead of performing modular division in order to compute , we need an alternative. We can use a segment tree or balanced binary search tree (similar to this problem) that stores the prime factors. When moving from to , we need to remove some prime factors, and add some. For more details, refer to the editorial from that problem.

Time Complexity: or better

For the last subtask, , meaning that even is too slow. We need a sub-linear algorithm. With some mathematical insight, we can show that (If you want a formal proof, bother Ninjaclasher on Slack). Thus, we can use Exponentiation By Squaring to precompute the values needed for the xor operation as well.

Time Complexity: 