分数: 575 点
问题陈述
给你正整数 N,M 和非负整数序列 A=(A_1,A_2,\ldots,A_N) 长度 N.
查找 \displaystyle \sum_{x=0}^{M-1} \min_{1\le i\le N} \left(x\oplus A_i \right).
在这里, x\oplus A_i 表示按位 \mathrm{XOR} of x 和 A_i.
什么是按位 \mathrm{XOR} 操作?
按位 \mathrm{XOR} 非负整数 X,Y, X \oplus Y,定义如下:
- 当 X \oplus Y 以二进制形式写入,其中的数字 2^k (k \geq 0)地方是 1 如果恰好是其中之一 X,Y 有 1 在 当以二进制形式写入时,位于 2^k 位置,并且 0 否则。
约束
- 1\le N\le 2\times 10^5
- 1\le M\le 10^9
- 0\le A_i \le 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M A_1 A_2 \ldots A_N
输出
输出答案。
样本输入 1
2 4 1 2
示例输出 1
2
- 当 x=0: x\oplus A_1=1,x\oplus A_2= 2,所以 \displaystyle \min_{1\le i\le N} \left(x\oplus A_i \right) = 1.
- 当 x=1: x\oplus A_1=0,x\oplus A_2= 3,所以 \displaystyle \min_{1\le i\le N} \left(x\oplus A_i \right) = 0.
- 当 x=2: x\oplus A_1=3,x\oplus A_2= 0,所以 \displaystyle \min_{1\le i\le N} \left(x\oplus A_i \right) = 0.
- 当 x=3: x\oplus A_1=2,x\oplus A_2= 1,所以 \displaystyle \min_{1\le i\le N} \left(x\oplus A_i \right) = 1.
因此,输出 1+0+0+1=2.
示例输入 2
6 5 0 1 2 3 4 5
示例输出 2
0
示例输入 3
10 8762 347 883 264 816 533 306 190 880 624 279
示例输出 3
34912221