問題一覧 > 通常問題

No.1969 XOR Equation

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 9
作問者 : chineristACchineristAC / テスター : hamamuhamamu
2 ProblemId : 7744 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-06-03 21:17:15

問題文

非負整数 $x,\ y$ に対し $x \oplus y$ で $x$ と $y$ のビットごとの排他的論理和を表すものとします。

$N$ 個の非負整数 $A_i\ (1\le i \le N)$ と非負整数 $Y$ が与えられます。非負整数 $X$ であって

$\displaystyle (X+A_1) \oplus (X+A_2) \oplus \dots \oplus (X+A_N)=Y$

を満たすものが存在するか判定し、存在する場合はそのような $X$ の最小値を求めてください。

$T$ 個のテストケースについて求めてください。

入力

はじめにテストケースの個数 $T$ が $1$ 行目に入力で与えられます。

$T$

つづけて $T$ 個のテストケースがそれぞれ以下の形式で与えられます。

$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}$
  • 全テストケースにおける $N$ の総和は $10^4$ 以下
  • 与えられる入力はすべて整数

出力

$T$ 行出力してください。 $i$ 行目には $i$ 番目のテストケースについて、上記の式を満たす非負整数 $X$ が存在しない場合は $-1$ と出力し、存在する場合はそのような $X$ の最小値を出力してください。

最後に改行してください。

サンプル

サンプル1
入力
3
3 13
5 6 7
3 7
0 1 5
10 533340073480221948
6909864066929986 33438018583964515 227723618264542569 238985354956723849 254406176055236004 292680002975784463 348601041566486647 440183079926366369 513218014800355096 538601892063016176
出力
5
-1
260777402535862300

$1$ つ目のテストケースについて、 $(5+5) \oplus (5+6) \oplus (5+7)=13$ です。 $5$ 未満の整数 $X$ であって上記の式を満たすものは存在しないので答えは $5$ になります。

$2$ つ目のテストケースについて、 上記の式を満たす $X$ は存在しません。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。