分数: 500 点
问题陈述
对于两个序列 S 和 T 长度 N 组成 0 和 1,让我们定义 f(S, T) 如下:
-
考虑重复以下操作 S 这样 S 将等于 T. f(S, T) 是这些操作的最小可能总成本。
- 更改 S_i (来自 0 to 1 或反之亦然)。该操作的成本是 D \times C_i,其中 D 是整数的个数 j 这样 S_j \neq T_j (1 \leq j \leq N) 就在此更改之前。
有 2^N \times (2^N - 1) 对 (S, T) 不同长度的序列 N 组成 0 和 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
有两对 (S, T) 不同长度的序列 2 组成 0 和 1,如下:
- S = (0), T = (1): 通过改变 S_1 to 1,我们可以有 S = T 的代价是 1000000000,所以 f(S, T) = 1000000000.
- S = (1), T = (0): 通过改变 S_1 to 0,我们可以有 S = T 的代价是 1000000000,所以 f(S, T) = 1000000000.
这些的总和是 2000000000,我们应该打印它的模数 (10^9+7),即 999999993.
示例输入 2
2 5 8
示例输出 2
124
有 12 对 (S, T) 不同长度的序列 3 组成 0 和 1,其中包括:
- S = (0, 1), T = (1, 0)
在这种情况下,如果我们首先改变 S_1 to 1 然后改变 S_2 to 0,总成本为 5 \times 2 + 8 = 18。我们不能有 S = T 以较小的成本,所以 f(S, T) = 18.
示例输入 3
5 52 67 72 25 79
示例输出 3
269312