SuSu is a fox spirit who is on her first matchmaking assignment. As a fox spirit, she must help to reunite reincarnated soulmates to fall in love again. Moreover, she must restore their memories by combining the two halves of their "sacrificial artifact" which they were reincarnated with.
However, when she is looking for their sacrificial artifact, the magical water pearl, SuSu realizes there is a problem: she doesn't know what the pearl looks like. Thus, she interrupted Bai Yuechu's speed dating to ask him for help. After promising him candy, he accepted her offer.
SuSu leads him to a row of half-pearls, with a runic inscription of the numbers on each respective pearl. Bai Yuechu has done some research and knows that the numbers on the two half pearls he is looking for fits the following constraints:
Let the two numbers be and
(Bitwise OR of and is )
(Bitwise AND of and is )
(Bitwise XOR of and is )
The definitions for bitwise OR, AND and XOR are at the bottom of the problem statement if you do not know these terms already.
Given , , in the input, Bai Yuechu wants you to determine the number of ordered pairs such that the conditions are satisfied.
Line 1: 3 integers , , and ()
110 44 66
The four pairs which satisfy the problem are , , , .
All three functions use the binary representation of the number. In binary representation, each digit is one or zero, and each digits' value is worth twice the previous digit. (Note that in our regular decimal number system, each digit is worth ten times the previous digit).
To perform each of these functions, first convert the numbers to binary. Then, compare each bit of the numbers.
The bit of is one if the bit of either or is .
The bit of ( and ) is one if the bit of both and is .
The bit of ( xor ) is one if the bit of is different from the bit of .
Note that these functions already exist in nearly every programming language.
For example, in C++, Java, Python and Pascal, bitwise OR is
|, bitwise AND is
& and bitwise XOR is