codeforces#P1770F. Koxia and Sequence
Koxia and Sequence
Description
Mari has three integers $n$, $x$, and $y$.
Call an array $a$ of $n$ non-negative integers good if it satisfies the following conditions:
- $a_1+a_2+\ldots+a_n=x$, and
- $a_1 \, | \, a_2 \, | \, \ldots \, | \, a_n=y$, where $|$ denotes the bitwise OR operation.
The score of a good array is the value of $a_1 \oplus a_2 \oplus \ldots \oplus a_n$, where $\oplus$ denotes the bitwise XOR operation.
Koxia wants you to find the total bitwise XOR of the scores of all good arrays. If there are no good arrays, output $0$ instead.
The first line of input contains three integers $n$, $x$ and $y$ ($1 \leq n < 2^{40}$, $0 \leq x < 2^{60}$, $0 \leq y < 2^{20}$).
Output a single integer — the total bitwise XOR of the scores of all good arrays.
Input
The first line of input contains three integers $n$, $x$ and $y$ ($1 \leq n < 2^{40}$, $0 \leq x < 2^{60}$, $0 \leq y < 2^{20}$).
Output
Output a single integer — the total bitwise XOR of the scores of all good arrays.
3 5 3
100 0 100
79877974817 749875791743978 982783
2
0
64
Note
In the first test case, there are $12$ good arrays totally as follows.
- $[0,2,3]$, $[0,3,2]$, $[2,0,3]$, $[2,3,0]$, $[3,0,2]$ and $[3,2,0]$ — the score is $0 \oplus 2 \oplus 3 = 1$;
- $[1, 2, 2]$, $[2, 1, 2]$ and $[2, 2, 1]$ — the score is $1 \oplus 2 \oplus 2 = 1$;
- $[1, 1, 3]$, $[1, 3, 1]$ and $[3, 1, 1]$ — the score is $1 \oplus 1 \oplus 3 = 3$.
Therefore, the total bitwise xor of the scores is $\underbrace{1 \oplus \ldots \oplus 1}_{9\text{ times}} \oplus 3 \oplus 3 \oplus 3 = 2$.
In the second test case, there are no good sequences. The output should be $0$.