Change a Little Bit

题目描述

对于两个由 $0$ 和 $1$ 组成且长度为 $N$ 的序列 $S$ 和 $T$，定义 $f(S, T)$ 如下：

考虑对 $S$ 反复进行以下操作直到 $S$ 等于 $T$。$f(S, T)$ 是这些操作的最小可能总代价。

改变 $S_i$（从 $0$ 变为 $1$ 或反之）。此操作的代价是 $D \times C_i$，其中 $D$ 是在该次改变之前满足 $S_j \neq T_j\ (1 \leq j \leq N)$ 的整数 $j$ 的个数。

共有 $2^N \times (2^N - 1)$ 对不同的长度为 $N$ 的由 $0$ 和 $1$ 组成的序列 $(S, T)$。计算对所有这些序列对 $f(S, T)$ 的和，对 $(10^9+7)$ 取模。

输入格式

输入以标准输入给出，格式如下： $N$ $C_1$ $C_2$ $\cdots$ $C_N$

输出格式

输出对所有 $f(S, T)$ 的和，对 $(10^9+7)$ 取模。

1
1000000000

999999993

2
5 8

124

5
52 67 72 25 79

269312

提示

$1 \leq N \leq 2 \times 10^5$ $1 \leq C_i \leq 10^9$ 输入中的所有数值均为整数。长度为 $2$ 的由 $0$ 和 $1$ 组成的不同序列对有两对，如下：

$S = (0), T = (1):$ 将 $S_1$ 改为 $1$ 即可使 $S = T$，代价为 $1000000000$，因此 $f(S, T) = 1000000000$。 $S = (1), T = (0):$ 将 $S_1$ 改为 $0$ 即可使 $S = T$，代价为 $1000000000$，因此 $f(S, T) = 1000000000$。

它们的和为 $2000000000$，对 $(10^9+7)$ 取模后为 $999999993$。
长度为 $3$ 的不同序列对共有 $12$ 对，其中包括：

$S = (0, 1), T = (1, 0)$

在这种情况下，如果我们先把 $S_1$ 改为 $1$ 然后把 $S_2$ 改为 $0$，总代价为 $5 \times 2 + 8 = 18$。不能以更小的代价使 $S = T$，所以 $f(S, T) = 18$.

标签: AtCoder|abc150E

来源

AtCoder|abc150E