Codeforces Round 917 (Div. 2) |
---|
Закончено |
Вам даны перестановка $$$p_0, p_1, \ldots, p_{n-1}$$$ нечётных чисел от $$$1$$$ до $$$2n-1$$$ и перестановка $$$q_0, q_1, \ldots, q_{k-1}$$$ целых чисел от $$$0$$$ до $$$k-1$$$.
Определим массив $$$a_0, a_1, \ldots, a_{nk-1}$$$ длины $$$nk$$$ в соответствии со следующим правилом:
Например, если $$$p = [3, 5, 1]$$$ и $$$q = [0, 1]$$$, то $$$a = [3, 6, 5, 10, 1, 2]$$$.
Обратите внимание, что все массивы в условии нумеруются с нуля. Также обратите внимание, что каждый элемент массива $$$a$$$ определён однозначно.
Найдите количество инверсий в массиве $$$a$$$. Так как ответ может быть очень большим, выведите его по модулю $$$998\,244\,353$$$.
Инверсией в массиве $$$a$$$ называется пара $$$(i, j)$$$ ($$$0 \le i < j < nk$$$), такая что $$$a_i > a_j$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора содержит два числа $$$n$$$ и $$$k$$$ ($$$1 \le n, k \le 2 \cdot 10^5$$$) — длины массивов $$$p$$$ и $$$q$$$.
Вторая строка каждого набора содержит $$$n$$$ различных целых чисел $$$p_0, p_1, \ldots, p_{n-1}$$$ ($$$1 \le p_i \le 2n-1$$$, $$$p_i$$$ нечётно) — массив $$$p$$$.
Третья строка каждого набора содержит $$$k$$$ различных целых чисел $$$q_0, q_1, \ldots, q_{k-1}$$$ ($$$0 \le q_i < k$$$) — массив $$$q$$$.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$, и что сумма $$$k$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно число — количество инверсий в массиве $$$a$$$ по модулю $$$998\,244\,353$$$.
43 23 5 10 13 41 3 53 2 0 11 510 1 2 3 48 35 1 7 11 15 3 9 132 0 1
9 25 0 104
В первом наборе входных данных массив $$$a$$$ равен $$$[3, 6, 5, 10, 1, 2]$$$. В нём есть $$$9$$$ инверсий: $$$(0, 4)$$$, $$$(0, 5)$$$, $$$(1, 2)$$$, $$$(1, 4)$$$, $$$(1, 5)$$$, $$$(2, 4)$$$, $$$(2, 5)$$$, $$$(3, 4)$$$, $$$(3, 5)$$$. Обратите внимание, что здесь перечислены пары $$$(i, j)$$$, такие что $$$i < j$$$ и $$$a_i > a_j$$$.
Во втором наборе входных данных массив $$$a$$$ равен $$$[8, 4, 1, 2, 24, 12, 3, 6, 40, 20, 5, 10]$$$. В нём $$$25$$$ инверсий.
В третьем наборе входных данных массив $$$a$$$ равен $$$[1, 2, 4, 8, 16]$$$. В нём нет инверсий.
Название |
---|