問題一覧 > 通常問題

No.1969 XOR Equation

レベル : / AI推定難易度 : 2500 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 8
作問者 : chineristAC / テスター : 👑 hamamu
お気に入りにしたユーザー ProblemId : 7744 / 自分の提出
問題文最終更新日: 2025-02-02 01:51:15
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 346 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。