AtCoder Beginner Contest 150
翻译中…
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)$.
翻译中…
样例
Input #1
1
1000000000
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$.
Input #2
2
5 8
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$.
Input #3
5
52 67 72 25 79
Output #3
269312
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。