← 返回题目列表

AtCoder · abc425_g

G. XOR 最小值之和

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

分数: 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 否则。
例如, 3 \oplus 5 = 6 (二进制表示形式: 011 \oplus 101 = 110).

约束

  • 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