406252: GYM102331 B Bitwise Xor

Zhong Ziqian got an integer array $$$a_1, a_2, \ldots, a_n$$$ and an integer $$$x$$$ as birthday presents.

Every day after that, he tried to find a non-empty subsequence of this array $$$1 \leq b_1 < b_2 < \ldots < b_k \leq n$$$, such that for all pairs $$$(i, j)$$$ where $$$1 \leq i < j \leq k$$$, the inequality $$$a_{b_i} \oplus a_{b_j} \geq x$$$ held. Here, $$$\oplus$$$ is the bitwise exclusive-or operation.

Of course, every day he must find a different subsequence.

How many days can he do this without repeating himself? As this number may be very large, output it modulo $$$998\,244\,353$$$.

The first line of the input contains two integers $$$n$$$ and $$$x$$$ ($$$1 \leq n \leq 300\,000$$$, $$$0 \leq x \leq 2^{60}-1$$$). Here, $$$n$$$ is the size of the array.

The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$: the array itself ($$$0 \leq a_i \leq 2^{60}-1$$$).

Output one integer: the number of subsequences of Ziqian's array such that bitwise xor of every pair of elements is at least $$$x$$$, modulo $$$998\,244\,353$$$.

3 0
0 1 2

7

3 2
0 1 2

5

3 3
0 1 2

4

7 4
11 5 5 8 3 1 3

35

In the first example, all $$$2^3-1$$$ non-empty subsequences are suitable.

in the second example, two non-empty subsequences are not suitable, it is $$$b = [1, 2]$$$ and $$$b = [1, 2, 3]$$$, that is because $$$a_1 \oplus a_2 = 0 \oplus 1 = 1$$$ which is smaller than $$$2$$$.

In the third example, $$$b = [1], b = [2], b = [3], b = [2, 3]$$$ are suitable.