[AGC016D] XOR Replace
题意翻译
题意:一个序列,一次操作可以将某个位置变成整个序列的异或和。 问最少几步到达目标序列。
题目描述
[problemUrl]: https://atcoder.jp/contests/agc016/tasks/agc016_d
長さ $ N $ の数列 $ a\ =\ (a_1,\ a_2,\ ...,\ a_N) $ があります。 ただし、各 $ a_i $ は $ 0 $ 以上の整数です。
すぬけ君は次の操作を繰り返し行うことができます。
- $ a $ のすべての要素の XOR を $ x $ とする。 整数 $ i $ ($ 1\ <\ =\ i\ <\ =\ N $) をひとつ選び、$ a_i $ を $ x $ に置き換える。
すぬけ君の目標は、$ a $ を数列 $ b\ =\ (b_1,\ b_2,\ ...,\ b_N) $ に一致させることです。 ただし、各 $ b_i $ は $ 0 $ 以上の整数です。
目標が達成可能か判定し、達成可能ならば必要な操作回数の最小値を求めてください。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ a_1 $ $ a_2 $ $ ... $ $ a_N $ $ b_1 $ $ b_2 $ $ ... $ $ b_N $
输出格式
目標が達成可能ならば、必要な操作回数の最小値を出力せよ。 達成不可能ならば、代わりに `-1` を出力せよ。
输入输出样例
输入样例 #1
3
0 1 2
3 1 0
输出样例 #1
2
输入样例 #2
3
0 1 2
0 1 2
输出样例 #2
0
输入样例 #3
2
1 1
0 0
输出样例 #3
-1
输入样例 #4
4
0 1 2 3
1 0 3 2
输出样例 #4
5
说明
### 制約
- $ 2\ <\ =\ N\ <\ =\ 10^5 $
- $ a_i $, $ b_i $ は整数である。
- $ 0\ <\ =\ a_i,\ b_i\ <\ 2^{30} $
### Sample Explanation 1
最初、$ a $ のすべての要素の XOR は $ 3 $ です。 $ a_1 $ を選んで $ 3 $ に置き換えると、$ a\ =\ (3,\ 1,\ 2) $ となります。 次に、$ a $ のすべての要素の XOR は $ 0 $ です。 $ a_3 $ を選んで $ 0 $ に置き換えると、$ a\ =\ (3,\ 1,\ 0) $ となり、$ b $ に一致します。