← 返回题目列表

AtCoder · arc127_d

D. 异或最小值之和

中文机器翻译题面 查看原题

分数: 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