/ 
Time Limit: 2.5 sec / Memory Limit: 1024 MiB
配点 : 575 点
問題文
正整数 N,M と長さ N の非負整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。
\displaystyle \sum_{x=0}^{M-1} \min_{1\le i\le N} \left(x\oplus A_i \right) を求めてください。
ただし、 x\oplus A_i は x と A_i のビット単位 \mathrm{XOR} を表します。
ビット単位 \mathrm{XOR} 演算とは
非負整数 X,Y のビット単位 \mathrm{XOR} 、X \oplus Y は、以下のように定義されます。
- X \oplus Y を二進表記した際の 2^k (k \geq 0) の位の数は、X,Y を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 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
Score : 575 points
Problem Statement
You are given positive integers N,M and a sequence of non-negative integers A=(A_1,A_2,\ldots,A_N) of length N.
Find \displaystyle \sum_{x=0}^{M-1} \min_{1\le i\le N} \left(x\oplus A_i \right).
Here, x\oplus A_i represents the bitwise \mathrm{XOR} of x and A_i.
What is bitwise \mathrm{XOR} operation?
The bitwise \mathrm{XOR} of non-negative integers X,Y, X \oplus Y, is defined as follows:
- When X \oplus Y is written in binary, the digit in the 2^k (k \geq 0) place is 1 if exactly one of X,Y has 1 in the 2^k place when written in binary, and 0 otherwise.
Constraints
- 1\le N\le 2\times 10^5
- 1\le M\le 10^9
- 0\le A_i \le 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M A_1 A_2 \ldots A_N
Output
Output the answer.
Sample Input 1
2 4 1 2
Sample Output 1
2
- When x=0: x\oplus A_1=1,x\oplus A_2= 2, so \displaystyle \min_{1\le i\le N} \left(x\oplus A_i \right) = 1.
- When x=1: x\oplus A_1=0,x\oplus A_2= 3, so \displaystyle \min_{1\le i\le N} \left(x\oplus A_i \right) = 0.
- When x=2: x\oplus A_1=3,x\oplus A_2= 0, so \displaystyle \min_{1\le i\le N} \left(x\oplus A_i \right) = 0.
- When x=3: x\oplus A_1=2,x\oplus A_2= 1, so \displaystyle \min_{1\le i\le N} \left(x\oplus A_i \right) = 1.
Therefore, output 1+0+0+1=2.
Sample Input 2
6 5 0 1 2 3 4 5
Sample Output 2
0
Sample Input 3
10 8762 347 883 264 816 533 306 190 880 624 279
Sample Output 3
34912221