← 返回题目列表

Codeforces · 1946/D

D. 生日礼物

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

Yarik 的生日即将到来,Mark 决定给他一个长度为 $$$n$$$ 的数组 $$$a$$$。

Mark 知道 Yarik 非常喜欢按位运算,而且他也有一个最喜欢的数字 $$$x$$$,所以 Mark 想找到最大的数字 $$$k$$$,这样就可以选择数字对 [$$$l_1, r_1$$$], [$$$l_2, r_2$$$], $$$\ldots$$$ [$$$l_k, r_k$$$],这样:

- $$$l_1 = 1$$$。
- $$$r_k = n$$$。
- $$$l_i \le r_i$$$ 适用于从 $$$1$$$ 到 $$$k$$$ 的所有 $$$i$$$。
- $$$r_i + 1 = l_{i + 1}$$$ 对于从 $$$1$$$ 到 $$$k - 1$$$ 的所有 $$$i$$$。
- $$$(a_{l_1} \oplus a_{l_1 + 1} \oplus \ldots \oplus a_{r_1}) | (a_{l_2} \oplus a_{l_2 + 1} \oplus \ldots \oplus a_{r_2}) | \ldots | (a_{l_k} \oplus a_{l_k + 1} \oplus \ldots \oplus a_{r_k}) \le x$$$,其中$$$\oplus$$$表示按位异或运算,$$$|$$$表示按位或运算。

如果这样的$$$k$$$不存在,则输出$$$-1$$$。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。以下行包含测试用例的描述。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$x$$$ ($$$1 \le n \le 10^5, 0 \le x < 2^{30}$$$) - 分别是数组 $$$a$$$ 的长度和数字 $$$x$$$。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i < 2^{30}$$$) - 数组 $$$a$$$ 本身。

保证所有测试用例的 $$$n$$$ 值的总和不超过 $$$10^5$$$。

输出

对于每个测试用例,在单独的行上输出一个整数 - 最大合适数字 $$$k$$$,如果 $$$k$$$ 不存在,则输出 $$$-1$$$。

示例

输入 #1

8
3 1
1 2 3
2 2
1 1
2 2
1 3
2 3
0 0
3 2
0 0 1
4 2
1 3 3 7
2 2
2 3
5 0
0 1 2 2 1

输出 #1

2
2
1
2
3
-1
1
2

注意

在第一个测试用例中,您可以将 $$$k$$$ 等于 $$$2$$$ 并选择两个段 [$$$1, 1$$$] 和 [$$$2, 3$$$],$$$(1) | (2 \oplus 3) = 1$$$。可以证明 $$$2$$$ 是最大可能的答案。

在第二个测试用例中,段 [$$$1, 1$$$] 和 [$$$2, 2$$$] 是合适的,$$$(1) | (1) = 1$$$。不可能制作更多的段。

在第三个测试用例中,不可能选择 $$$2$$$ 段,如 $$$(1) | (3) = 3 > 2$$$,因此最佳答案是$$$1$$$。