Codeforces Round 970 (Div. 3) |
---|
Закончено |
У Сакурако есть коробка, в которой $$$n$$$ мячей. Каждый мяч имеет свою стоимость. Она хочет поспорить со своим другом, что если он наугад выберет из коробки два мяча (это могут быть два разных мяча, но они могут иметь одинаковое значение), то произведение их значений будет равно числу, которое загадала Сакурако.
Так как Сакурако имеет докторскую степень по теории вероятностей, она знает, что наилучшее число для выбора — это математическое ожидание, но она забыла, как его вычислить. Помогите Сакурако и найдите математическое ожидание произведения двух элементов из массива.
Можно показать, что математическое ожидание имеет вид $$$\frac{P}{Q}$$$, где $$$P$$$ и $$$Q$$$ — неотрицательные целые числа, а $$$Q \ne 0$$$. Сообщите значение $$$P \cdot Q^{-1}(\bmod 10^9+7)$$$.
Первая строка содержит одно целое число $$$t$$$ ($$$1\le t\le 10^4$$$) — количество наборов входных данных.
Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$2\le n\le 2\cdot 10^5$$$) — количество элементов массива.
Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0\le a_i\le 10^9$$$) — элементы массива.
Гарантируется, что сумма $$$n$$$ по всем наборам не превысит $$$2\cdot 10^5$$$.
Для каждого набора входных данных выведите значение $$$P \cdot Q^{-1}(\bmod 10^9+7)$$$.
333 2 342 2 2 451 2 3 4 5
7 6 500000012
Для первого теста друг Сакурако может выбрать такие пары шаров: $$$(a_1,a_2)$$$, $$$(a_1,a_3)$$$, $$$(a_2,a_3)$$$. Их произведение равно $$$3\cdot 2=6$$$, $$$3\cdot 3=9$$$, $$$3\cdot 2=6$$$ соответственно, поэтому математическое ожидание равно $$$\frac{6+9+6}{3}=7$$$.
Для второго теста друг Сакурако может выбрать такие пары шаров: $$$(a_1,a_2)$$$, $$$(a_1,a_3)$$$, $$$(a_1,a_4)$$$, $$$(a_2,a_3)$$$, $$$(a_2,a_4)$$$, $$$(a_3,a_4)$$$. Их произведение равно $$$2\cdot 2=4$$$, $$$2\cdot 2=4$$$, $$$2\cdot 4=8$$$, $$$2\cdot 2=4$$$, $$$2\cdot 4=8$$$, $$$2\cdot 4=8$$$ соответственно, поэтому математическое ожидание равно $$$\frac{4+4+8+4+8+8}{6}=\frac{36}{6}=6$$$.
Название |
---|