CF1817E.Half-sum
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You're given a multiset of non-negative integers {a1,a2,…,an} .
In one step you take two elements x and y of the multiset, remove them and insert their mean value 2x+y back into the multiset.
You repeat the step described above until you are left with only two numbers A and B . What is the maximum possible value of their absolute difference ∣A−B∣ ?
Since the answer is not an integer number, output it modulo 109+7 .
输入格式
Each test contains multiple test cases. The first line contains the number of test cases t ( 1≤t≤100 ). Description of the test cases follows.
The first line of each test case contains a single integer n ( 2≤n≤106 ) — the size of the multiset.
The second line contains n integers a1,a2,…,an ( 0≤ai≤109 ) — the elements of the multiset.
It is guaranteed that the sum of n over all test cases does not exceed 106 .
输出格式
For each test case, output a single integer, the answer to the problem modulo 109+7 .
Formally, let M=109+7 . It can be shown that the answer can be expressed as an irreducible fraction qp , where p and q are integers and q≡0(modM) . Output the integer equal to p⋅q−1modM . In other words, output an integer x such that 0≤x<M and x⋅q≡p(modM) .
输入输出样例
输入#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
说明/提示
In the first case, you can't do any operations, so the answer is ∣7−3∣=4 .
In the second case, one of the optimal sequence of operations:
- Substitute 1 and 2 with 1.5 ;
- Substitute 10 and 11 with 10.5 ;
- The difference between 1.5 and 10.5 is 9 .
In the third case, the exact answer is 23 , and 500000005⋅2≡3(mod109+7) .