← 返回题目列表

Codeforces · 1616/H

H. 保持 XOR 低电平

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

给定一个数组 $$$a_1, a_2, \ldots, a_n$$$ 和一个整数 $$$x$$$。

求此数组 $$$1 \leq b_1 < b_2 < \ldots < b_k \leq n$$$ 索引的非空子集的数量,这样对于所有对 $$$(i, j)$$$ 其中 $$$1 \leq i < j \leq k$$$,不等式 $$$a_{b_i} \oplus a_{b_j} \leq x$$$ 被持有。这里,$$$\oplus$$$表示按位异或运算。由于答案可能非常大,因此输出它对 $$$998\,244\,353$$$ 取模。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$x$$$ ($$$1 \leq n \leq 150\,000$$$, $$$0 \leq x < 2^{30}$$$)。这里,$$$n$$$ 是数组的大小。

下一行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i < 2^{30}$$$):数组本身。

输出

打印一个整数:非空子集的数量,使得每对元素的按位异或最多为 $$$x$$$,模 $$$998\,244\,353$$$。

示例

输入 #1

4 2
0 1 2 3

输出 #1

8

输入 #2

3 6
4 2 2

输出 #2

7

输入 #3

4 0
1 1 2 2

输出 #3

6