Problem Description

[CSP-J 2026] 按位与 / and（民间数据）

题目描述

小 R 有 $n$ 个非负整数 $a_1,a_2,\ldots,a_n$。

小 X 给了小 R 一个正整数 $m$，并要求小 R 从这 $n$ 个非负整数中选出恰好 $m$ 个，使得选出的 $m$ 个数的二进制按位与的值最大。

你需要帮助小 R 求出，他能选出的 $m$ 个数的按位与的最大值。

输入格式

从文件 and.in 中读入数据。

输入的第一行包含两个正整数 $n,m$。

输入的第二行包含 $n$ 个非负整数 $a_1,a_2,\ldots,a_n$，依次表示小 R 的 $n$ 个非负整数。

输出格式

输出到文件 and.out 中。

输出一行一个非负整数，表示小 R 能选出的 $m$ 个数的按位与的最大值。

样例

样例 1

输入：

4 2
3 15 12 12

输出：

12

样例 2

输入：

5 3
31 3 1 15 7

输出：

7

说明与数据范围

时间限制：1000 ms 内存限制：1024 MiB（源字段为 KiB）

样例 1 解释

小 R 有 $4$ 个非负整数：$3,15,12,12$。

• 若小 R 选择 $3,15$，则按位与的值为 $3\mathbin{\mathrm{and}}15=3$；
• 若小 R 选择 $3,12$，则按位与的值为 $3\mathbin{\mathrm{and}}12=0$；
• 若小 R 选择 $15,12$，则按位与的值为 $15\mathbin{\mathrm{and}}12=12$；
• 若小 R 选择 $12,12$，则按位与的值为 $12\mathbin{\mathrm{and}}12=12$。

因此，小 R 能选出的 $m$ 个数的按位与的最大值为 $12$。

样例 2 解释

若小 R 选择 $31,15,7$，则按位与的值为 $31\mathbin{\mathrm{and}}15\mathbin{\mathrm{and}}7=7$。可以证明，小 R 能选出的 $m$ 个数的按位与的最大值为 $7$。

样例 3

见题目目录下的 and/3.in 与 and/3.ans。

该样例满足测试点 $8\sim 10$ 的约束条件。

样例 4

见题目目录下的 and/4.in 与 and/4.ans。

该样例满足测试点 $14,15$ 的约束条件。

样例 5

见题目目录下的 and/5.in 与 and/5.ans。

该样例满足测试点 $18,19$ 的约束条件。

数据范围

对于所有测试数据，均有：

• $1\le m\le n\le 2\times 10^5$；
• 对于所有 $i$（$1\le i\le n$），均有 $0\le a_i<2^{30}$。

::cute-table{tuack} | 测试点编号 | $n\le$ | $m$ | $\max_{i=1}^{n}a_i<$ | 特殊性质 | | :-: | :-: | :-: | :-: | :-: | | $1\sim 5$ | $20$ | $\le n$ | $2^{20}$ | 无 | | $6$ | $2000$ | $=1$ | $2^{20}$ | 无 | | $7$ | $2000$ | $=n$ | $2^{20}$ | 无 | | $8\sim 10$ | $2000$ | $=2$ | $2^{20}$ | 无 | | $11,12$ | $2\times 10^5$ | $=n-1$ | $2^{20}$ | 无 | | $13$ | $2\times 10^5$ | $\le n$ | $2^{20}$ | A | | $14,15$ | $2\times 10^5$ | $\le n$ | $2^{20}$ | B | | $16,17$ | $2\times 10^5$ | $\le n$ | $4$ | 无 | | $18,19$ | $2\times 10^5$ | $\le n$ | $2^{10}$ | 无 | | $20$ | $2\times 10^5$ | $\le n$ | $2^{30}$ | 无 |

特殊性质 A：对于所有 $i$（$1\le i\le n$），均存在非负整数 $k_i$ 满足 $a_i=2^{k_i}-1$。

特殊性质 B：存在非负整数 $k$ 满足 $n=2^k$，且对所有 $i$（$1\le i\le n$），均有 $a_i=i-1$。

Source

CSP-J 2026