分数: 700 点
问题陈述
给出的是序列 N 整数: (A_1,A_2,\cdots,A_N) 和 (B_1,B_2,\cdots,B_N).
查找 \sum_{1 \leq i < j \leq N} \min(A_i \oplus A_j, B_i \oplus B_j),其中 \oplus 表示按位异或。
约束
- 1 \leq N \leq 250000
- 0 \leq A_i,B_i < 2^{18}
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \cdots A_N B_1 B_2 \cdots B_N
输出
打印答案。
示例输入 1
3 1 2 3 4 5 6
示例输出 1
4
- \min(1 \oplus 2, 4 \oplus 5)=\min(3,1)=1
- \min(1 \oplus 3, 4 \oplus 6)=\min(2,2)=2
- \min(2 \oplus 3, 5 \oplus 6)=\min(1,3)=1
因此,答案是 1+2+1=4.
示例输入 2
4 1 2 3 4 1 2 3 4
示例输出 2
24
示例输入 3
10 195247 210567 149398 9678 23694 46151 187762 17915 176476 249828 68649 128425 249346 62366 194119 117620 26327 161384 207 57656
示例输出 3
4019496