18469번 - Bitwise Xor 다국어

Zhong Ziqian got an integer array a₁, a₂, . . . , 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 ≤ b₁ < b₂ < . . . < b_k ≤ n, such that for all pairs (i, j) where 1 ≤ i < j ≤ k, the inequality a_bi ⊕ a_bj ≥ x held. Here, ⊕ 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 ≤ n ≤ 300 000, 0 ≤ x ≤ 2⁶⁰ − 1). Here, n is the size of the array.

The next line contains n integers a₁, a₂, . . . , a_n: the array itself (0 ≤ a_i ≤ 2⁶⁰ − 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.

In the first example, all 2³ − 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₁ ⊕ a₂ = 0 ⊕ 1 = 1 which is smaller than 2.

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