Задача №114667. Задача для третьеклассника
Маленький Тайлер зашел на кухню и увидел, что на холодильнике магнитиками выложена строка \(s\). Он сразу увидел её безграничный потенциал!
Тайлеру нравятся строки, особенно те, которые лексикографически меньше строки \(t\). Играя с магнитиками на холодильнике, он задумался, а сколько различных строк, лексикографически меньших строки \(t\) он может собрать, переставляя буквы в строке \(s\). Так как он учится всего лишь во втором классе, он не может этого посчитать, поэтому просит вас о помощи!
Напомним, что строка \(x\) лексикографически меньше строки \(y\), если выполнено одно из двух условий:
- существует такая позиция символа \(m\), присутствующая в обеих строках, что до \(m\)-го символа строки совпадают, а \(m\)-й символ строки \(x\) меньше \(m\)-го символа \(y\),
- строка \(x\) является строгим префиксом \(y\) (то есть получается отбрасыванием одного или больше символов с конца строки \(y\)).
Так как ответ может быть слишком большим, выведите его по модулю \(998\,244\,353\).
В первой строке даны два целых числа \(n\) и \(m\) (\(1 \le n, m \le 200\,000\)) — длины строк \(s\) и \(t\) соответственно.
Во второй строке даны \(n\) целых чисел \(s_1, s_2, s_3 \ldots s_n\) (\(1 \le s_i \le 200\,000\)) — буквы строки \(s\).
Во второй строке даны \(m\) целых чисел \(t_1, t_2, t_3 \ldots t_m\) (\(1 \le t_i \le 200\,000\)) — буквы строки \(t\).
Выведите единственное число — количество строк, лексикографически меньших \(t\), которые можно получить, переставляя буквы в \(s\), по модулю \(998\,244\,353\).
В первом примере интересующие нас строки это [1 2 2] и [2 1 2]. Строка [2 2 1] лексикографически больше строки [2 1 2 1] — по-этому её мы не считаем.
Во втором примере подходят все строки, кроме [4 3 2 1], так что их \(4! - 1 = 23\)
В третем примере подходит только строка [1 1 1 2]
Тесты к этой задаче состоят из 6 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, прохождение тестов из условия не требуется для некоторых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
| Доп. ограничения | |||||
| Группа | Баллы | \(n, m\) | \(s_i, t_i\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | Тесты из условия. |
| 1 | 16 | \(n, m \le 10\) | \(s_i, t_i \le 10\) | 0 | |
| 2 | 15 | – | \(s_i, t_i \le 2\) | – | |
| 3 | 11 | – | \(s_i, t_i \le 20\) | 0 – 2 | |
| 4 | 13 | – | \(s_i, t_i \le 200\) | 0 – 3 | |
| 5 | 12 | – | – | – | В каждой из строк (по отдельности) все буквы различны |
| 6 | 33 | – | – | 0 – 5 | Offline-проверка. |
3 4 1 2 2 2 1 2 1
2
4 4 1 2 3 4 4 3 2 1
23
4 3 1 1 1 2 1 1 2
1