← 返回题目列表

AtCoder · awc0011_c

C. 团队成员最大数量

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

分数: 300 分

问题陈述

高桥负责组建编程竞赛团队。有 N 候选人,编号自 1 to N.

每位候选人 i 表示他们精通的技能集,以非负整数的位表示形式 A_i。高桥想从这些人中挑选团队成员 N 这样的人,当使用按位或组合所有选定成员的技能时,团队的整体技能集与目标值完全匹配 K.

高桥希望团队中包含尽可能多的人。

找到可以从候选者的非空子集中选择的最大候选者数,使得所有技能值的按位或完全等于 K。如果不存在这样的子集,则输出 -1.

约束

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq K \leq 10^{18}
  • 0 \leq A_i \leq 10^{18}
  • 所有输入值均为整数。

输入

N K
A_1 A_2 \ldots A_N
  • 第一行包含 N,候选人数量,以及 K,目标 OR 值,以空格分隔。
  • 第二行包含技能值 每个候选者的 A_1, A_2, \ldots, A_N ,用空格分隔。

输出

在一行中输出候选者的非空子集中的最大元素数,其技能值的按位或完全等于 K。如果不存在这样的子集,则输出 -1.


示例输入 1

5 7
3 5 6 1 9

示例输出 1

4

示例输入 2

4 3
4 8 16 32

示例输出 2

-1

示例输入 3

10 15
1 2 4 8 3 5 15 6 16 14

示例输出 3

9