[ABC091D] Two Sequences
题意翻译
给你长度为 $n$ 的两串序列 $a,b$
求 $a,b$ 两序列各任取一数相加形成的 $n^2$ 个和的 $\operatorname{xor}$ 和
$1\le n \le 200000$
$0\le a_i<2^{28}$
题目描述
[problemUrl]: https://atcoder.jp/contests/abc091/tasks/arc092_b
$ 2 $ つの長さ $ N $ の非負整数列 $ a_1,\ ...,\ a_N,\ b_1,\ ...,\ b_N $ が与えられます。
$ 1\ \leq\ i,\ j\ \leq\ N $ となるように整数 $ i,\ j $ を選ぶ方法は $ N^2 $ 通りありますが,この $ N^2 $ 通りの $ i,\ j $ それぞれについて,$ a_i\ +\ b_j $ を計算し,紙に書き出します。 つまり,紙に $ N^2 $ 個の整数を書きます。
この $ N^2 $ 個の整数のxorを計算してください。
xorの説明
整数 $ c_1,\ c_2,\ ...,\ c_m $ のxor $ X $ は,以下のように定義されます。
- $ X $ を $ 2 $ 進数表記したときの $ 2^k $($ 0\ \leq\ k $, $ k $ は整数)の位の値は,$ c_1,\ c_2,\ ...c_m $ のうち,$ 2 $ 進数表記したときの $ 2^k $ の位の値が $ 1 $ となるものの個数が奇数個ならば $ 1 $,偶数個ならば $ 0 $ となります
例えば,$ 3 $ と $ 5 $ のxorの値は,$ 3 $ の $ 2 $ 進数表記が $ 011 $,$ 5 $ の $ 2 $ 進数表記が $ 101 $ のため,$ 2 $ 進数表記が $ 110 $ の $ 6 $ となります。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ a_1 $ $ a_2 $ $ ... $ $ a_N $ $ b_1 $ $ b_2 $ $ ... $ $ b_N $
输出格式
求めた結果を出力せよ。
输入输出样例
输入样例 #1
2
1 2
3 4
输出样例 #1
2
输入样例 #2
6
4 6 0 0 3 3
0 5 6 5 0 3
输出样例 #2
8
输入样例 #3
5
1 2 3 4 5
1 2 3 4 5
输出样例 #3
2
输入样例 #4
1
0
0
输出样例 #4
0
说明
### 制約
- 入力は全て整数
- $ 1\ \leq\ N\ \leq\ 200,000 $
- $ 0\ \leq\ a_i,\ b_i\ <\ 2^{28} $
### Sample Explanation 1
紙には $ 4(1+3),\ 5(1+4),\ 5(2+3),\ 6(2+4) $ の $ 2^2\ =\ 4 $ つの数が書かれます。