/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
0, 1 からなる長さ N の異なる 2 つの数列 S, T に対し、関数 f(S, T) を以下のように定めます。
-
S に対し以下の操作を繰り返して T と等しくすることを考える。このとき行う操作のコストの和として考えられる最小の値が f(S, T) である。
- S_i を (0 から 1、もしくは 1 から 0 に) 変更する。この操作のコストは、変更の直前に S_j \neq T_j (1 \leq j \leq N) であったような整数 j の個数を D として、D \times C_i である。
0, 1 からなる長さ N の異なる 2 つの数列の組 (S, T) は 2^N \times (2^N - 1) 通り考えられます。これらすべてに対する f(S, T) の和を 10^9+7 で割った余りを計算してください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq C_i \leq 10^9
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N C_1 C_2 \cdots C_N
出力
f(S, T) の和を 10^9+7 で割った余りを出力せよ。
入力例 1
1 1000000000
出力例 1
999999993
0, 1 からなる長さ 1 の異なる 2 つの数列の組 (S, T) は以下の 2 通りが考えられます。
-
S = (0), T = (1): S_1 を 1 に変更することでコスト 1000000000 で S = T とできるため、f(S, T) = 1000000000 です。
-
S = (1), T = (0): S_1 を 0 に変更することでコスト 1000000000 で S = T とできるため、f(S, T) = 1000000000 です。
これらの和は 2000000000 であり、これを 10^9+7 で割った余りは 999999993 です。
入力例 2
2 5 8
出力例 2
124
0, 1 からなる長さ 2 の異なる 2 つの数列の組 (S, T) は 12 通り存在し、例えば以下のものが考えられます。
- S = (0, 1), T = (1, 0)
この場合、1 回目の操作で S_1 を 1 に変更し、2 回目の操作で S_2 を 0 に変更するとき、操作のコストの和は 5 \times 2 + 8 = 18 です。これより小さいコストで S = T とすることはできないので、f(S, T) = 18 です。
入力例 3
5 52 67 72 25 79
出力例 3
269312
Score : 500 points
Problem Statement
For two sequences S and T of length N consisting of 0 and 1, let us define f(S, T) as follows:
-
Consider repeating the following operation on S so that S will be equal to T. f(S, T) is the minimum possible total cost of those operations.
- Change S_i (from 0 to 1 or vice versa). The cost of this operation is D \times C_i, where D is the number of integers j such that S_j \neq T_j (1 \leq j \leq N) just before this change.
There are 2^N \times (2^N - 1) pairs (S, T) of different sequences of length N consisting of 0 and 1. Compute the sum of f(S, T) over all of those pairs, modulo (10^9+7).
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq C_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N C_1 C_2 \cdots C_N
Output
Print the sum of f(S, T), modulo (10^9+7).
Sample Input 1
1 1000000000
Sample Output 1
999999993
There are two pairs (S, T) of different sequences of length 2 consisting of 0 and 1, as follows:
- S = (0), T = (1): by changing S_1 to 1, we can have S = T at the cost of 1000000000, so f(S, T) = 1000000000.
- S = (1), T = (0): by changing S_1 to 0, we can have S = T at the cost of 1000000000, so f(S, T) = 1000000000.
The sum of these is 2000000000, and we should print it modulo (10^9+7), that is, 999999993.
Sample Input 2
2 5 8
Sample Output 2
124
There are 12 pairs (S, T) of different sequences of length 3 consisting of 0 and 1, which include:
- S = (0, 1), T = (1, 0)
In this case, if we first change S_1 to 1 then change S_2 to 0, the total cost is 5 \times 2 + 8 = 18. We cannot have S = T at a smaller cost, so f(S, T) = 18.
Sample Input 3
5 52 67 72 25 79
Sample Output 3
269312