Задача №115224. Ультра mex
Рассмотрим \(A\) — множество неотрицательных целых чисел. Минимальное неотрицательное целое число, которое не встречается в \(A\), обозначим как \(\mathrm{mex}(A)\). Например, \(\mathrm{mex}(\{0, 1, 2, 4, 5, 9\}) = 3\). Эта функция часто используется, например, в теории игр.
Операция «побитовое исключающее или» (обозначается « xor » в Паскале, « ^ » в C++, Python и Java) для двух целых чисел определена следующим образом: \(i\)-й бит результата равен \(1\) тогда и только тогда, когда в одном из чисел этот бит \(1\), а в другом \(0\). Будем обозначать эту операцию символом \(\oplus\). Например, \(6 \oplus 10 = 110_2 \oplus 1010_2 = 1100_2 = 12\).
Определим ещё одну операцию над множеством \(A\), содержащим число \(0\). Операция будет называться «ультра». Пусть \(m = \mathrm{mex}(A)\). Заметим, что \(m > 0\). Построим новое множество \(\mathrm{ultra}(A)\) следующим образом: применим «побитовое исключающее или» с числом \((m - 1)\) ко всем элементам \(A\). Например, \(\mathrm{ultra}(\{0, 1, 2, 4, 5, 9\}) = \{0 \oplus 2, 1 \oplus 2, 2\oplus 2, 4\oplus 2, 5\oplus 2, 9\oplus 2\}=\{2, 3, 0, 6, 7, 11\} = \{0, 2, 3, 6, 7, 11\}\). Можно показать, что если множество \(A\) содержит \(0\), то множество \(\mathrm{ultra}(A)\) также содержит \(0\).
Выберем множество \(A_0\), состоящее из целых чисел от \(0\) до \(2^k-1\) и содержащее \(0\). Рассмотрим следующую последовательность:
- \(m_0 = \mathrm{mex}(A_0)\), \(A_1 = \mathrm{ultra}(A_0)\)
- \(m_1 = \mathrm{mex}(A_1)\), \(A_2 = \mathrm{ultra}(A_1)\)
- ...
- \(m_i = \mathrm{mex}(A_i)\), \(A_{i + 1} = \mathrm{ultra}(A_i)\)
- ...
Будем называть множество \(A_0\) \(\mathrm{mex}\)-стабильным , если начиная с некоторого индекса \(l\) числа \(m_i\) перестают меняться. То есть, для всех \(i \ge l\) выполнено \(m_i = m_l\). Число \(m_l\) будем называть \(\mathrm{mex}\)-пределом множества \(A_0\).
Вам даны числа \(k\), \(n\) и \(p\). Вычислите количество множеств \(A_0\), которые:
- Состоят из \(n\) различных чисел от \(0\) до \(2^k - 1\) (\(0\) обязательно должен входить в \(A_0\));
- Являются \(\mathrm{mex}\)-стабильными;
- \(\mathrm{mex}\)-предел \(A_0\) равен \(p\).
Так как ответ может быть большим, выведите его по простому модулю \(M\). Гарантируется, что \((M-1)\) делится на \(2^{18}\).
В первой строке дано одно целое число \(M\) — модуль, по которому нужно посчитать ответ (\(3 \leq M \leq 10^9\); \((M-1)\) делится на \(2^{18}\)). Гарантируется, что \(M\) простое число.
Во второй строке дано одно целое число \(t\) — количество наборов входных данных (\(1 \le t \le 100\,000\)).
Для каждого набора входных данных в единственной строке даны три целых числа \(k\), \(n\) и \(p\) (\(1 \le k \le 17\); \(1 \le n, p \le 2^k\)).
Для каждого набора входных данных на новой строке выведите одно целое число — количество искомых множеств \(A\), взятое по модулю \(M\).
В этой задаче \(30\) подзадач. В каждой подзадаче показывается первая ошибка.
В таблице ниже приведены ограничения на \(k\) и \(t\) в каждой подзадаче. Для каждой подзадачи необходимыми являются все другие подзадачи с не большими ограничениями на \(k\) и \(t\).
| \(t \leq 10\) | \(t \leq 10^5\) | |||
| \(k\) | Номер | Баллы | Номер | Баллы |
| \(k \leq 1\) | 1 | 3 | – | – |
| \(k \leq 2\) | 2 | 5 | – | – |
| \(k \leq 3\) | 3 | 7 | – | – |
| \(k \leq 4\) | 4 | 8 | – | – |
| \(k \leq 5\) | 5 | 3 | 6 | 3 |
| \(k \leq 6\) | 7 | 3 | 8 | 3 |
| \(k \leq 7\) | 9 | 3 | 10 | 3 |
| \(k \leq 8\) | 11 | 2 | 12 | 2 |
| \(k \leq 9\) | 13 | 2 | 14 | 2 |
| \(k \leq 10\) | 15 | 3 | 16 | 3 |
| \(k \leq 11\) | 17 | 3 | 18 | 3 |
| \(k \leq 12\) | 19 | 3 | 20 | 3 |
| \(k \leq 13\) | 21 | 3 | 22 | 3 |
| \(k \leq 14\) | 23 | 3 | 24 | 3 |
| \(k \leq 15\) | 25 | 4 | 26 | 3 |
| \(k \leq 16\) | 27 | 4 | 28 | 3 |
| \(k \leq 17\) | 29 | 4 | 30 | 3 |
Всего существует \(7\) \(\mathrm{mex}\)-стабильных множеств размера \(2\) из чисел от \(0\) до \(7\): \(\{0, 1\}\), \(\{0, 2\}\), \(\{0, 3\}\), \(\{0, 4\}\), \(\{0, 5\}\), \(\{0, 6\}\), \(\{0, 7\}\).
Для \(\{0, 1\}\): \(\mathrm{mex}(\{0, 1\})\) = 2, \(\mathrm{ultra}(\{0, 1\})=\{0 \oplus 1, 1 \oplus 1\} = \{1, 0\} = \{0, 1\}\), получается, что \(A_1 = A_0\). Значит \(\mathrm{mex}\)-предел будет равен \(2\).
Для всех остальных множеств \(m_0 = \mathrm{mex}(A_0)=1\), для них при вычислении ultra происходит \(\oplus\) с числом 0, поэтому \(\mathrm{ultra}(A_0) = A_0\). Получается, для них \(\mathrm{mex}\)-предел равен \(\mathrm{mex}(A_0) = 1\).
998244353 6 3 2 1 3 2 2 3 2 3 3 2 4 3 5 1 4 6 1
6 1 0 0 29 2461