#cspjf2026t3. 按位与(and)

按位与(and)

按位与(and)

题目描述

​ 小 R 有 n 个非负整数 a1,a2,…,ana_1,a_2,…,a_n。

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

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

输入格式

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

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

​ 输入的第二行包含 n 个非负整数a1,a2,…,an a_1,a_2,…,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

说明/提示

样例 1 解释

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

  • 若小 R 选择 3,15,则按位与的值为 3 and 15=3;
  • 若小 R 选择 3,12,则按位与的值为 3 and 12=0;
  • 若小 R 选择 15,12,则按位与的值为 15 and 12=12;
  • 若小 R 选择 12,12,则按位与的值为 12 and 12=12。

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

样例 2 解释

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

样例 3

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

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

样例 4

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

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

样例 5

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

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

【数据范围】

对于所有测试数据,均有:

  • 1≤m≤n≤2×1051≤m≤n≤2×10^5;
  • 对于所有 i(1≤i≤n)i(1≤i≤n),均有 0≤ai<2300≤a_i<2^{30}。
测试点编号 n≤ m maxi=1nai<max_{i=1}^na_i< 特殊性质
1∼5 20 ≤n 2202^{20} 无
6 2000 =1
7 =n
8∼10 =2
11,12 2×1052×10^5 =n−1
13 ≤n A
14,15 B
16,17 4 无
18,19 2102^{10}
20 2302^{30}

特殊性质 A:对于所有i(1≤i≤n) i(1≤i≤n),均存在非负整数 kik_i 满足 ai=2ki−1a_i=2^{k_i}−1。s

特殊性质 B:存在非负整数 k 满足 n=2kn=2^k,且对所有i(1≤i≤n) i(1≤i≤n),均有 ai=i−1a_i=i−1