No.1969 XOR Equation
タグ : / 解いたユーザー数 8
作問者 :
hamamu
Problem Statement
For non-negative integers $x,\ y$, let $x \oplus y$ denote the bitwise exclusive OR of $x$ and $y$.
You are given $N$ non-negative integers $A_i\ (1\le i \le N)$ and a non-negative integer $Y$. Determine whether there exists a non-negative integer $X$ satisfying
$\displaystyle (X+A_1) \oplus (X+A_2) \oplus \dots \oplus (X+A_N)=Y$
and, if one exists, find the minimum such $X$.
Solve this for $T$ test cases.
Input
First, the number of test cases $T$ is given on line $1$ of the input.
$T$
Then, $T$ test cases follow, each given in the following format.
$N$ $Y$ $A_1$ $A_2$ $\dots$ $A_N$
- $1 \le T \le 10^4$
- $1 \le N \le 10^4$
- $0 \le Y < 2^{60}$
- $0 \le A_i < 2^{60}$
- The sum of $N$ over all test cases is at most $10^4$
- All input values are integers
Output
Print $T$ lines. On line $i$, for the $i$-th test case, print $-1$ if there is no non-negative integer $X$ satisfying the above equation; otherwise, print the minimum such $X$.
Print a newline at the end.
Sample
Sample 1
Input
3 3 13 5 6 7 3 7 0 1 5 10 533340073480221948 6909864066929986 33438018583964515 227723618264542569 238985354956723849 254406176055236004 292680002975784463 348601041566486647 440183079926366369 513218014800355096 538601892063016176
Output
5 -1 260777402535862300
For test case $1$, $(5+5) \oplus (5+6) \oplus (5+7)=13$. There is no integer $X$ less than $5$ satisfying the above equation, so the answer is $5$.
For test case $2$, there is no $X$ satisfying the above equation.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。