Задача №115380. Максимальная попарная разница
Вам даны два массива чисел длины \(n\): \(a_1, a_2, \ldots, a_n\) и \(b_1, b_2, \ldots, b_n\). При этом известно, что все числа \(a_1, a_2, \ldots, a_n, b_1, b_2, \ldots, b_n\) попарно различны.
Назовём счётом перестановки \(p_1, p_2, \ldots, p_n\) длины \(n\) значение следующего выражения: \(\lvert a_1 - b_{p_1} \rvert + \lvert a_2 - b_{p_2} \rvert + \ldots + \lvert a_n - b_{p_n} \rvert\).
Вам нужно найти максимально возможный счёт по всем перестановкам длины \(n\), а также количество перестановок длины \(n\), имеющих этот максимальный счёт. Так как количество перестановок может быть достаточно большим, требуется найти только его остаток при делении на \(10^9 + 7\). Обратите внимание, что от самого максимально возможного счёта не нужно брать остаток.
Напомним, что перестановкой длины \(n\) является массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) — перестановка, но \([1,2,2]\) не перестановка (\(2\) встречается в массиве дважды) и \([1,3,4]\) тоже не перестановка (\(n=3\), но в массиве встречается \(4\)).
Первая строка содержит одно целое число \(n\) (\(1 \le n \le 50\,000\)) — длина массивов \(a\) и \(b\).
Вторая строка содержит \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^9\)) — элементы массива \(a\).
Третья строка содержит \(n\) целых чисел \(b_1, b_2, \ldots, b_n\) (\(1 \le b_i \le 10^9\)) — элементы массива \(b\).
Гарантируется, что все числа \(a_1, a_2, \ldots, a_n, b_1, b_2, \ldots, b_n\) попарно различны. То есть, для любых \(1 \le i, j \le n\) верно, что \(a_i \neq b_j\), а также \(a_i \ne a_j\) и \(b_i \ne b_j\) при \(i \ne j\).
Выведите два целых числа — максимально возможный счёт и количество перестановок с этим счётом. Количество перестановок выведите по модулю \(10^9 + 7\). От самого максимально возможного счёта не нужно брать остаток.
В данной задаче \(50\) тестов, помимо тестов из условия, каждый из них оценивается в \(2\) балла. Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования.
Решения, корректно работающие при \(n \leq 10\), наберут не менее \(16\) баллов.
Решения, корректно работающие при \(n \leq 18\), наберут не менее \(30\) баллов.
Решения, корректно работающие при \(n \leq 1000\), наберут не менее \(50\) баллов.
Дополнительно, решения, корректно работающие при \(b_i = a_i+1\) для всех \(1 \leq i \leq n\), наберут не менее \(14\) баллов.
Дополнительно, решения, корректно работающие при \(b_{i+1}=b_i+1\) для всех \(1 \leq i < n\), наберут не менее \(14\) баллов.
Рассмотрим первый пример. Всего есть \(2\) перестановки длины \(2\):
-
\(p = [1, 2]\). Счёт перестановки равен \(|a_1 - b_1| + |a_2 - b_2| = |1 - 2| + |3 - 4| = 2\).
-
\(p = [2, 1]\). Счёт перестановки равен \(|a_1 - b_2| + |a_2 - b_1| = |1 - 4| + |3 - 2| = 4\).
Максимальный счёт равен \(4\), и он достигается только на одной перестановке.
Рассмотрим второй пример. Всего есть \(6\) перестановок длины \(3\):
-
\(p = [1, 2, 3]\). Счёт перестановки равен \(|10 - 7| + |15 - 12| + |6 - 14| = 14\).
-
\(p = [1, 3, 2]\). Счёт перестановки равен \(|10 - 7| + |15 - 14| + |6 - 12| = 10\).
-
\(p = [2, 1, 3]\). Счёт перестановки равен \(|10 - 12| + |15 - 7| + |6 - 14| = 18\).
-
\(p = [2, 3, 1]\). Счёт перестановки равен \(|10 - 12| + |15 - 14| + |6 - 7| = 4\).
-
\(p = [3, 1, 2]\). Счёт перестановки равен \(|10 - 14| + |15 - 7| + |6 - 12| = 18\).
-
\(p = [3, 2, 1]\). Счёт перестановки равен \(|10 - 14| + |15 - 12| + |6 - 7| = 8\).
Максимальный счёт равен \(18\), и есть \(2\) перестановки, на которых достигается этот счёт.
2 1 3 2 4
4 1
3 10 15 6 7 12 14
18 2
2 1 7 1000000000 998244353
1998244345 2
5 82 494 27 39390 999999999 83 495 28 39391 1000000000
2000078561 12
8 10 20 30 40 50 60 70 80 32 33 34 35 36 37 38 39
184 720