Задача №114968. Соберите станок
Станок состоит из \(n\) деталей первого типа, пронумерованных от \(1\) до \(n\), и из \(n\) деталей второго типа, пронумерованных от \(1\) до \(n\). Деталь первого типа под номером \(i\) имеет размер \(a_i\), а деталь под номером \(i\) второго типа имеет размер \(b_i\).
Для сборки станка необходимо каждую деталь первого типа соединить с какой-то деталью второго типа, при том разные детали первого типа надо соединить с разными деталями второго типа. Качеством станка считается количество пар соединённых деталей, в которых размер детали первого типа строго больше размера детали второго типа.
Вася даёт вам число \(m\) и просит для каждого числа \(k\) от \(m\) до \(n\) посчитать количество способов собрать станок качества равного \(k\), взятое по модулю \(998244353\). Два способа считаются различными, если есть пара деталей, соединённая в одном из способов, но несоединённая в другом.
Первая строка содержит два целых числа \(n\) и \(m\) (\(1 \le n \le 100\,000,\ 0 \le m \le n\)) — количество деталей каждого из типов, а так же данное Васей число.
Вторая строка содержит \(n\) чисел \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^9\)) — размеры деталей первого типа.
Третья строка содержит \(n\) чисел \(b_1, b_2, \ldots, b_n\) (\(1 \le b_i \le 10^9\)) — размеры деталей второго типа.
Выведите \(n - m + 1\) число. \(i\)-е число должно быть равно количеству способов собрать станок качества \(m + i - 1\), взятое по модулю \(998244353\).
Тесты к этой задаче состоят из 8 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, прохождение тестов из условия не требуется для некоторых групп.
| Доп. ограничения | ||||||
| Группа | Баллы | \(n\) | \(m\) | \(a_i\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | – | Тесты из условия. |
| 1 | 8 | \(n \le 9\) | – | – | 0 | |
| 2 | 11 | \(n \le 17\) | – | – | 0, 1 | |
| 3 | 14 | – | – | \(a_i \le 2\) | – | |
| 4 | 17 | – | \(m = n\) | – | – | |
| 5 | 19 | – | \(m = n-1\) | – | – | |
| 6 | 16 | \(n \le 300\) | – | – | 0, 1, 2 | |
| 7 | 15 | \(n \le 5000\) | – | – | 0, 1, 2, 6 | |
| 8 | 1 | – | – | – | 0 – 7 | |
5 0 2 3 4 5 6 1 2 3 4 5
0 1 26 66 26 1
4 2 1 2 3 4 4 3 2 1
11 1 0
2 0 2 2 1 1
0 0 2