CF1946D Birthday Gift

Yarik 的生日快到了，Mark 决定送给他一个长度为 $n$ 的数组 $a$。 Mark 知道 Yarik 非常喜欢位运算，并且他还有一个最喜欢的数字 $x$，所以 Mark 想要找到最大的整数 $k$，使得可以选择 $k$ 对数对 $[l_1, r_1]$、$[l_2, r_2]$、$\ldots$、$[l_k, r_k]$，满足： - $l_1 = 1$。 - $r_k = n$。 - 对于所有 $i$，$l_i \le r_i$。 - 对于所有 $i$，$r_i + 1 = l_{i + 1}$，$1 \le i < k$。 - $(a_{l_1} \oplus a_{l_1 + 1} \oplus \ldots \oplus a_{r_1}) \mid (a_{l_2} \oplus a_{l_2 + 1} \oplus \ldots \oplus a_{r_2}) \mid \ldots \mid (a_{l_k} \oplus a_{l_k + 1} \oplus \ldots \oplus a_{r_k}) \le x$，其中 $\oplus$ 表示按位异或运算，$\mid$ 表示按位或运算。 如果不存在这样的 $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$。

在第一个测试用例中，可以取 $k=2$，选择两个区间 $[1, 1]$ 和 $[2, 3]$，$(1) \mid (2 \oplus 3) = 1$。可以证明 $2$ 是最大可能的答案。 在第二个测试用例中，区间 $[1, 1]$ 和 $[2, 2]$ 合适，$(1) \mid (1) = 1$。无法再分更多的区间。 在第三个测试用例中，无法选择 $2$ 个区间，因为 $(1) \mid (3) = 3 > 2$，所以最优答案是 $1$。 由 ChatGPT 4.1 翻译