分数: 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