← 返回题目列表

Codeforces · 1669/H

H. 最大与

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

设 $$$\mathsf{AND}$$$ 表示按位 AND 运算,$$$\mathsf{OR}$$$ 表示按位 OR 运算。

给定一个长度为 $$$n$$$ 的数组 $$$a$$$ 和一个非负整数 $$$k$$$。您最多可以对以下类型的数组执行 $$$k$$$ 操作:

- 选择索引 $$$i$$$ ($$$1 \leq i \leq n$$$) 并将 $$$a_i$$$ 替换为 $$$a_i$$$ $$$\mathsf{OR}$$$ $$$2^j$$$,其中 $$$j$$$ 是 $$$0$$$ 到 $$$30$$$ 之间的任何整数(含)。换句话说,在操作中,您可以选择索引 $$$i$$$ ($$$1 \leq i \leq n$$$) 并将 $$$a_i$$$ 的第 $$$j$$$ 位设置为 $$$1$$$ ($$$0 \leq j \leq 30$$$)。

执行最多 $$$k$$$ 运算后,输出 $$$a_1$$$ $$$\mathsf{AND}$$$ $$$a_2$$$ $$$\mathsf{AND}$$$ $$$\dots$$$ $$$\mathsf{AND}$$$ $$$a_n$$$ 的最大可能值。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le k \le 10^9$$$)。

接下来是一行,包含描述数组 $$$a$$$ 的 $$$n$$$ 整数 ($$$0 \leq a_i < 2^{31}$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一行,其中包含 $$$a_1$$$ 的最大可能 $$$\mathsf{AND}$$$ 值 $$$\mathsf{AND}$$$ $$$a_2$$$ $$$\mathsf{AND}$$$ $$$\dots$$$ $$$\mathsf{AND}$$$ $$$a_n$$$ 执行最多 $$$k$$$ 操作后。

示例

输入 #1

4
3 2
2 1 1
7 0
4 6 6 28 6 6 12
1 30
0
4 4
3 1 3 1

输出 #1

2
4
2147483646
1073741825

注意

对于第一个测试用例,我们可以使用 $$$2$$$ 操作设置最后 $$$2$$$ 元素的位 $$$1$$$ ($$$2^1$$$),从而获得数组 [$$$2$$$, $$$3$$$, $$$3$$$],其 $$$\mathsf{AND}$$$ 值等于$$$2$$$。

对于第二个测试用例,我们无法执行任何操作,因此答案只是整个数组的 $$$\mathsf{AND}$$$,即 $$$4$$$。