시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 8 4 4 50.000%

문제

Zhong Ziqian got an integer array a1, a2, . . . , an and an integer x as birthday presents.

Every day after that, he tried to find a non-empty subsequence of this array 1 ≤ b1 < b2 < . . . < bk ≤ n, such that for all pairs (i, j) where 1 ≤ i < j ≤ k, the inequality abi ⊕ abj ≥ 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 ≤ 260 − 1). Here, n is the size of the array.

The next line contains n integers a1, a2, . . . , an: the array itself (0 ≤ ai ≤ 260 − 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.

예제 입력 1

3 0
0 1 2

예제 출력 1

7

예제 입력 2

3 2
0 1 2

예제 출력 2

5

예제 입력 3

3 3
0 1 2

예제 출력 3

4

예제 입력 4

7 4
11 5 5 8 3 1 3

예제 출력 4

35

힌트

In the first example, all 23 − 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 a1 ⊕ a2 = 0 ⊕ 1 = 1 which is smaller than 2.

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

출처

Camp > Petrozavodsk Programming Camp > Summer 2019 > Day 2 B번

  • 문제를 만든 사람: 300iq