/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
高橋君はプログラミングコンテストのチーム編成を担当しています。候補者は N 人おり、 1 から N までの番号が付けられています。
各候補者 i は、自分が得意とするスキルの集合を非負整数 A_i のビット表現で表しています。高橋君はこの N 人の中からチームメンバーを選び、選んだメンバー全員のスキルをビットごとのオア（OR）で合わせたとき、チーム全体のスキルセットがちょうど目標値 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
- 1 行目には、候補者の人数を表す N と、目標とするオアの値を表す K が、スペース区切りで与えられる。
- 2 行目には、各候補者のスキル値を表す A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
出力
選んだ候補者のスキル値のビットごとのオアがちょうど K となるような空でない部分集合のうち、要素数が最大のものの要素数を 1 行で出力せよ。そのような部分集合が存在しない場合は -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
Score : 300 pts
Problem Statement
Takahashi is in charge of forming teams for a programming contest. There are N candidates, numbered from 1 to N.
Each candidate i represents the set of skills they are proficient in as a bit representation of a non-negative integer A_i. Takahashi wants to select team members from these N people such that when the skills of all selected members are combined using bitwise OR, the team's overall skill set exactly matches the target value K.
Takahashi wants to include as many people as possible in the team.
Find the maximum number of candidates that can be selected from a non-empty subset of candidates such that the bitwise OR of all their skill values equals exactly K. If no such subset exists, output -1.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 0 \leq K \leq 10^{18}
- 0 \leq A_i \leq 10^{18}
- All input values are integers.
Input
N K A_1 A_2 \ldots A_N
- The first line contains N, the number of candidates, and K, the target OR value, separated by a space.
- The second line contains the skill values A_1, A_2, \ldots, A_N of each candidate, separated by spaces.
Output
Output in one line the maximum number of elements in a non-empty subset of candidates whose bitwise OR of skill values equals exactly K. If no such subset exists, output -1.
Sample Input 1
5 7 3 5 6 1 9
Sample Output 1
4
Sample Input 2
4 3 4 8 16 32
Sample Output 2
-1
Sample Input 3
10 15 1 2 4 8 3 5 15 6 16 14
Sample Output 3
9