Это сложная версия задачи. Разница между двумя версиями заключается в определении детерминированной max-кучи, ограничении на время и ограничениях на \(n\) и \(t\). Вы можете совершать взломы только в том случае, если решены обе версии задачи..
Рассмотрим полное бинарное дерево размером \(2^n - 1\), с вершинами, пронумерованными от \(1\) до \(2^n-1\), и корнем в \(1\). Для каждой вершины \(v\) (\(1 \le v \le 2^{n - 1} - 1\)) вершина \(2v\) является ее левым ребенком, а вершина \(2v + 1\) — ее правым ребенком. Каждой вершине \(v\) также присвоено значение \(a_v\).
Определим операцию \(\mathrm{pop}\) следующим образом:
- инициализировать переменную \(v\) как \(1\);
- повторять следующий процесс до тех пор, пока вершина \(v\) не станет листом (т.е. пока не выполняется \(2^{n - 1} \le v \le 2^n - 1\)):
- среди дочерних вершин \(v\) выбрать ту, значение которой больше, и обозначить такую вершину \(x\); если значения на них равны (то есть \(a_{2v} = a_{2v + 1}\)), то можно выбрать любую из них;
- присвоить \(a_x\) значению \(a_v\) (т.е. \(a_v := a_x\));
- присвоить \(x\) переменной \(v\) (т.е. \(v := x\));
- присвоить \(-1\) значению \(a_v\) (т.е. \(a_v := -1\)).
Мы говорим, что операция \(\mathrm{pop}\) является детерминированной, если существует единственный способ выполнить такую операцию. Другими словами, \(a_{2v} \neq a_{2v + 1}\) выполняется на каждом шаге операции.
Бинарное дерево называется max-кучей, если для каждой вершины \(v\) (\(1 \le v \le 2^{n - 1} - 1\)) выполняется \(a_v \ge a_{2v}\) и \(a_v \ge a_{2v + 1}\).
Максимальная куча является детерминированной, если операция \(\mathrm{pop}\) детерминирована для кучи, когда мы выполняем ее в первый и второй раз.
Изначально \(a_v := 0\) для каждой вершины \(v\) (\(1 \le v \le 2^n - 1\)), и ваша цель — посчитать количество различных детерминированных max-куч, которые можно получить в результате применения следующей операции \(\mathrm{add}\) ровно \(k\) раз:
- Выбрать целое число \(v\) (\(1 \le v \le 2^n - 1\)), и для каждой вершины \(x\) на пути между \(1\) и \(v\) прибавить \(1\) к \(a_x\).
Две кучи считаются разными, если есть вершина, которая имеет разные значения в этих кучах.
Поскольку ответ может быть очень большим, выведите его по модулю \(p\).
Выходные данные
Для каждого набора входных данных выведите единственную строку, содержащую целое число: количество различных детерминированных max-куч, которое можно получить в результате применения вышеупомянутой операции \(\mathrm{add}\) ровно \(k\) раз, по модулю \(p\).
Примечание
Для первого набора входных данных, если мы выберем \(v = 1\) и выполним операцию, у нас будет \(a = [1, 0, 0]\), а поскольку \(a_2 = a_3\), мы можем выбрать любой из них при выполнении первой операции \(\mathrm{pop}\), поэтому такая куча не является детерминированной max-кучей.
А если мы выберем \(v = 2\), у нас будет \(a = [1, 1, 0]\), то при выполнении первой операции \(\mathrm{pop}\) произойдет следующее:
- инициализировать \(v\) как \(1\)
- поскольку \(a_{2v} > a_{2v + 1}\), выбрать \(2v\) как \(x\), тогда \(x = 2\)
- присвоить \(a_x\) значению \(a_v\), тогда \(a = [1, 1, 0]\)
- присвоить \(x\) переменной \(v\), тогда \(v = 2\)
- поскольку \(v\) является листом, присвоить \(-1\) значению \(a_v\), тогда \(a = [1, -1, 0]\)
А во время второго \(\mathrm{pop}\) произойдет следующее:
- инициализировать \(v\) как \(1\)
- поскольку \(a_{2v} < a_{2v + 1}\), выбрать \(2v + 1\) в качестве \(x\), тогда \(x = 3\)
- присвоить \(a_x\) значению \(a_v\), тогда \(a = [0, -1, 0]\)
- присвоить \(x\) переменной \(v\), тогда \(v = 3\)
- поскольку \(v\) является листом, присвоить \(-1\) значению \(a_v\), тогда \(a = [0, -1, -1]\)
Поскольку и первая, и вторая операция \(\mathrm{pop}\) детерминированы, это детерминированная max-куча. Также, если мы выберем \(v = 3\), то \(a\) будет детерминированной max-кучей, так что ответ — \(2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
2 1 998244353
3 2 998244853
3 3 998244353
3 4 100000037
4 2 100000039
4 3 100000037
|
2
12
40
100
32
224
|
|
2
|
1
100 500 100000037
|
66681128
|
|
3
|
2
87 63 100000037
13 437 100000039
|
83566569
54517140
|