Codeforces Round 869 (Div. 1) |
---|
Закончено |
Вам дано мультимножество неотрицательных целых чисел $$$\{a_1, a_2, \dots, a_n\}$$$.
Вы можете выбрать два элемента $$$x$$$ и $$$y$$$ из мультимножества, удалить их и вставить их полусумму $$$\frac{x + y}{2}$$$ обратно в мультимножество.
Вы повторяете описанное выше действие до тех пор, пока не останется только два числа $$$A$$$ и $$$B$$$. Каково максимально возможное значение их абсолютной разности $$$|A-B|$$$?
Поскольку ответ не является целым числом, выведите его по модулю $$$10^9+7$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$). Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 10^6$$$) — размер мультимножества.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — элементы мультимножества.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$10^6$$$.
Для каждого набора входных данных выведите одно целое число — ответ на задачу по модулю $$$10^9+7$$$.
Формально, пусть $$$M = 10^9+7$$$. Можно показать, что ответ может быть представлен в виде несократимой дроби $$$\frac{p}{q}$$$, где $$$p$$$ и $$$q$$$ — целые числа, и $$$q \not \equiv 0 \pmod{M}$$$. Выведите целое число, равное $$$p \cdot q^{-1} \bmod M$$$. Другими словами, выведите такое целое число $$$x$$$, что $$$0 \le x < M$$$ и $$$x \cdot q \equiv p \pmod{M}$$$.
527 341 2 10 1131 2 3664 32 64 16 64 041 1 1 1
4 9 500000005 59 0
В первом примере вы не можете выполнить никаких операций, поэтому ответ равен $$$|7-3|=4$$$.
Во втором примере одна из оптимальных последовательностей операций выглядит так:
В третьем примере точный ответ равен $$$\frac{3}{2}$$$, и $$$500\,000\,005 \cdot 2 \equiv 3 \pmod{10^9+7}$$$.
Название |
---|