普及模拟赛 6 - E

问题描述

小 C 在打一款攻防游戏，他指挥的 A 国里有 $n$ 个士兵，第 $i$ 个士兵的攻击力为 $a_i$ ，防御力为 $b_i$ 。

由于游戏特性，可以将两个士兵进行组队，假设第 $x$ 个士兵和第 $y$ 个士兵进行组队，那么这组士兵的攻击力为 $a_x \oplus a_y$ ，防御力为 $b_x \oplus b_y$ ，其中 $\oplus$ 表示异或，由于短板效应，一组士兵的能力值定义为其攻击力和防御力的较小值，即 $\min(a_x \oplus a_y,b_x \oplus b_y)$ 。

现在小 C 需要在 $n$ 个士兵中选择两个不同士兵形成一组，他想知道在所有选择的可能中，所有可能的士兵组的能力值之和为多少。

输入格式

第一行包含一个正整数，表示 $n$ 。

第二行包含 $n$ 个整数，第 $i$ 个表示 $a_i$ 。

第三行包含 $n$ 个整数，第 $i$ 个表示 $b_i$ 。

输出格式

输出 $1$ 个整数，表示最终答案。

样例输入1

3
1 2 3
4 5 6

样例输出1

样例解释1

若选择 $1,2$ 士兵，能力值为 $(a_1 \oplus a_2,b_1 \oplus b_2)=\min(3,1)=1$ 。

若选择 $1,3$ 士兵，能力值为 $(a_1 \oplus a_3,b_1 \oplus b_3)=\min(2,2)=2$ 。

若选择 $2,3$ 士兵，能力值为 $(a_2 \oplus a_3,b_2 \oplus b_3)=\min(1,3)=1$ 。

因此答案之和为 $1+2+1=4$ 。

样例输入2

10
195247 210567 149398 9678 23694 46151 187762 17915 176476 249828
68649 128425 249346 62366 194119 117620 26327 161384 207 57656

样例输出2

评测数据规模

对于 $20\%$ 的数据， $1 \leq n \leq 5000$

对于另外 $30\%$ 的数据， $0 \leq a_i,b_i \leq 50$ 。

对于另外 $30\%$ 的数据， $a_i,b_i$ 均为 $2$ 的幂次。

对于所有测评数据， $1 \leq n \leq 2 \times 10^5,0 \leq a_i,b_i <2^{18}$ 。