← 返回题目列表

AtCoder · abc150_e

E. 改变一点

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

分数: 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