問題一覧 > 通常問題

No.3046 White Tiger vs Monster

レベル : / AI推定難易度 : 2450 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 2
作問者 : Naru820 / テスター : okkuu
お気に入りにしたユーザー ProblemId : 12116 / 自分の提出
問題文最終更新日: 2025-03-22 21:04:48
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original

Problem Statement

White Tiger is fighting $N$ monsters.

The health of the $i$-th monster is $A_i$. White Tiger's initial attack power is $B$.

White Tiger can attack a monster if and only if its current attack power is greater than or equal to the monster's health.

When White Tiger attacks a monster, that monster disappears. Furthermore, letting $X$ be White Tiger's attack power before the attack and $Y$ be the health of the attacked monster, White Tiger's attack power changes to $X \oplus Y$.

Here, $\oplus$ denotes bitwise exclusive OR.

If White Tiger chooses the order of attacking monsters optimally, what is the maximum number of monsters it can defeat?

Constraints

  • $1 \leq N \leq 2\times 10^5$
  • $1 \leq B \leq 10^{18}$
  • $1 \leq A_i \leq 10^{18}$

Input

The input is given from Standard Input in the following format.

$N\ B$
$A_1\ A_2 \ldots \ A_N$

Output

Print on one line the maximum number of monsters White Tiger can defeat.

Sample

Sample 1
Input
3 5
1 3 5
Output
3

White Tiger can defeat all 3 monsters as follows.

  • Defeat monster 2. White Tiger's attack power becomes $5 \oplus3 = 6$.
  • Defeat monster 3. White Tiger's attack power becomes $6 \oplus 5 = 3$.
  • Defeat monster 1. White Tiger's attack power becomes $3 \oplus 1 = 2$.

Therefore, the answer is $3$.

Sample 2
Input
2 1
1 2
Output
1
Sample 3
Input
15 49497
1964 616 419 161 9 2 6 19 49 49 4619649 16 19 16961 9619
Output
14

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。