← 返回题目列表

Codeforces · 1553/H

H. 异或和距离

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

给定一个数组 $$$a$$$,由 $$$n$$$ 不同元素和一个整数 $$$k$$$ 组成。数组中的每个元素都是一个不超过$$$2^k-1$$$的非负整数。

让我们将数字 $$$x$$$ 的 XOR 距离定义为

$$$$$$f(x) = \min\limits_{i = 1}^{n} \min\limits_{j = i + 1}^{n} |(a_i \oplus x) - (a_j \oplus x)|,$$$$$$

其中 $$$\oplus$$$ 表示按位异或运算。

对于从 $$$0$$$ 到 $$$2^k-1$$$ 的每个整数 $$$x$$$,您必须计算 $$$f(x)$$$。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le 19$$$; $$$2 \le n \le 2^k$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 2^k-1$$$)。所有这些整数都是不同的。

输出

打印 $$$2^k$$$ 整数。其中第 $$$i$$$ 应等于 $$$f(i-1)$$$。

示例

输入 #1

3 3
6 0 3

输出 #1

3 1 1 2 2 1 1 3

输入 #2

3 4
13 4 2

输出 #2

2 2 6 6 3 1 2 2 2 2 1 3 6 6 2 2

注意

考虑第一个例子:

- 对于$$$x = 0$$$,如果我们对数组中的元素与$$$x$$$进行按位异或,我们得到数组$$$[6, 0, 3]$$$,两个元素的最小绝对差为$$$3$$$;
- 对于$$$x = 1$$$,如果我们将数组中的元素与$$$x$$$进行按位异或,我们得到数组$$$[7, 1, 2]$$$,两个元素的最小绝对差为$$$1$$$;
- 对于$$$x = 2$$$,如果我们将数组中的元素与$$$x$$$进行按位异或,我们得到数组$$$[4, 2, 1]$$$,两个元素的最小绝对差为$$$1$$$;
- 对于$$$x = 3$$$,如果我们对数组中的元素与$$$x$$$进行按位异或,我们得到数组$$$[5, 3, 0]$$$,两个元素的最小绝对差为$$$2$$$;
- 对于$$$x = 4$$$,如果我们对数组中的元素与$$$x$$$进行按位异或,我们得到数组$$$[2, 4, 7]$$$,两个元素的最小绝对差为$$$2$$$;
- 对于$$$x = 5$$$,如果我们对数组中的元素与$$$x$$$进行按位异或,我们得到数组$$$[3, 5, 6]$$$,两个元素的最小绝对差为$$$1$$$;
- 对于$$$x = 6$$$,如果我们对数组中的元素与$$$x$$$进行按位异或,我们得到数组$$$[0, 6, 5]$$$,两个元素的最小绝对差为$$$1$$$;
- 对于$$$x = 7$$$,如果我们对数组的元素与$$$x$$$进行按位异或,我们得到数组$$$[1, 7, 4]$$$,两个元素的最小绝对差是$$$3$$$。