Вам дан массив целых чисел $$$a_1, a_2, \ldots, a_n$$$ и целое число $$$x$$$.
Найдите количество непустых подмножеств индексов этого массива $$$1 \leq b_1 \lt b_2 \lt \ldots \lt b_k \leq n$$$ таких, что для всех пар $$$(i, j)$$$, где $$$1 \leq i \lt 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 \lt 2^{30}$$$). Здесь $$$n$$$ — размер массива.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \lt 2^{30}$$$) — сам массив.
Выведите одно целое число: количество непустых подмножеств таких, что побитовое исключающее ИЛИ любых двух элементов не больше $$$x$$$, по модулю $$$998\,244\,353$$$.
4 2 0 1 2 3
8
3 6 4 2 2
7
4 0 1 1 2 2
6
| Good Bye 2021: 2022 is NEAR |
|---|
| Закончено |
