← 返回题目列表

Codeforces · 1817/E

E. 半和

中文机器翻译题面 查看原题

给你一个非负整数的多重集 $$$\{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}$$$。

示例

输入 #1

5
2
7 3
4
1 2 10 11
3
1 2 3
6
64 32 64 16 64 0
4
1 1 1 1

输出 #1

4
9
500000005
59
0

注意

第一种情况,你不能进行任何操作,所以答案是$$$|7-3|=4$$$。

在第二种情况下,最佳操作顺序之一:

1. 将 $$$1$$$ 和 $$$2$$$ 替换为 $$$1.5$$$;
2. 将 $$$10$$$ 和 $$$11$$$ 替换为 $$$10.5$$$;
3. $$$1.5$$$ 和 $$$10.5$$$ 之间的差异是 $$$9$$$。

在第三种情况下,确切答案是 $$$\frac{3}{2}$$$ 和 $$$500\,000\,005 \cdot 2 \equiv 3 \pmod{10^9+7}$$$。