DALTSUM - Descending Alternating Sums
Given an array A of k integers (not necessarily distinct), we define the descending alternating sum of this array, denoted F(A) the following way. First, we sort the array in descending order. Suppose the elements, after sorting, are A1 ≥ A2 ≥ ... ≥ Ak respectively. Then the descending alternating sum of array A is
F(A) = A1 - A2 + A3 - ... + (-1)k+1 Ak.
For example, if A = [5, -3, 8, 2, 0, -5] then after sorting it in descending order, we find A = [8, 5, 2, 0, -3, -5]. So the descending alternating sum of this array is 8 - 5 + 2 - 0 + (-3) - (-5) = 7. In particular, the descending alternating sum of an empty array is 0.
You are given an array A of n integers where 1 ≤ n ≤ 105 and |Ai| ≤ 1018. You have to print the sum of the descending alternating sums of all subsets of this array A (there are 2n of them) modulo M = 109 + 7. In other words, if the subsets of array A are S1, S2, ..., S2n then you have to print the sum
F(S1) + F(S2) + ... + F(S2n) modulo M = 109 + 7.
Note: we consider some integer modulo a positive integer to be non-negative. In the other words, the output R must satisfy the inequality 0 ≤ R < M.
Input
The first line of the input file contains a single integer n, denoting the size of the array A.
The second line contains n integers A1, A2, ..., An, the elements of the array A.
Output
Print a single integer, the sum of descending alternating sums of all subsets of the array A.
Example
Input: 3 -1 9 3
Output: 36
hide comments
Shubham Jadhav:
2017-05-17 17:39:49
Piece Of Cake if you figure out the solution @Mangesh |
|
himanshu_0896:
2016-10-09 18:36:11
if some elements are same,then no. of subsets wont be equal to pow(2.n), right ??
|
|
dwij28:
2016-10-08 12:04:09
Pen Paper + Modular Exponentiation = AC :) |
|
rezwanarefin:
2016-10-07 03:00:24
@tasmeemreza এখানে ও ok ok করা শুরু করছও ... o.O Last edit: 2016-10-07 03:01:59 |
|
:D:
2016-10-07 02:01:43
I'm pretty sure there are exactly 0 corner cases for this problem. The only thing to remember is that you need to have result in range <0;MOD). Modulo result can be negative. In C/C++, for example, you should do something like this:
|
|
agarwalg271:
2016-10-06 19:31:19
tasmeemreza please give testcase for corner case
|
|
tasmeemreza:
2016-10-06 17:01:42
ok |
Added by: | AlphaQ |
Date: | 2016-10-06 |
Time limit: | 0.300s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU |
Resource: | Self posed |