C. Do you want a date?

Codeforces

IDCF810C

Time2000ms

Memory256MB

Difficulty—

implementationmathsortings

English · Original

Chinese · Translation

Formal · Original

Leha decided to move to a quiet town Vičkopolis, because he was tired by living in Bankopolis. Upon arrival he immediately began to expand his network of hacked computers. During the week Leha managed to get access to _n_ computers throughout the town. Incidentally all the computers, which were hacked by Leha, lie on the same straight line, due to the reason that there is the only one straight street in Vičkopolis. Let's denote the coordinate system on this street. Besides let's number all the hacked computers with integers from 1 to _n_. So the _i_\-th hacked computer is located at the point _x__i_. Moreover the coordinates of all computers are distinct. Leha is determined to have a little rest after a hard week. Therefore he is going to invite his friend Noora to a restaurant. However the girl agrees to go on a date with the only one condition: Leha have to solve a simple task. Leha should calculate a sum of _F_(_a_) for all _a_, where _a_ is a non-empty subset of the set, that consists of all hacked computers. Formally, let's denote _A_ the set of all integers from 1 to _n_. Noora asks the hacker to find value of the expression . Here _F_(_a_) is calculated as the maximum among the distances between all pairs of computers from the set _a_. Formally, . Since the required sum can be quite large Noora asks to find it modulo 109 + 7. Though, Leha is too tired. Consequently he is not able to solve this task. Help the hacker to attend a date. ## Input The first line contains one integer _n_ (1 ≤ _n_ ≤ 3·105) denoting the number of hacked computers. The second line contains _n_ integers _x_1, _x_2, ..., _x__n_ (1 ≤ _x__i_ ≤ 109) denoting the coordinates of hacked computers. It is guaranteed that all _x__i_ are distinct. ## Output Print a single integer — the required sum modulo 109 + 7. [samples] ## Note There are three non-empty subsets in the first sample test:, and . The first and the second subset increase the sum by 0 and the third subset increases the sum by 7 - 4 = 3. In total the answer is 0 + 0 + 3 = 3. There are seven non-empty subsets in the second sample test. Among them only the following subsets increase the answer: , , , . In total the sum is (4 - 3) + (4 - 1) + (3 - 1) + (4 - 1) = 9.

Leha 决定搬到宁静的小镇 Vičkopolis，因为他厌倦了在 Bankopolis 的生活。到达后，他立即开始扩展自己黑入的计算机网络。在一周内，Leha 成功获取了小镇上 #cf_span[n] 台计算机的访问权限。巧合的是，所有被 Leha 黑入的计算机都位于同一条直线上，这是因为 Vičkopolis 只有一条笔直的街道。让我们在这条街上建立一个坐标系，并将所有被黑的计算机从 #cf_span[1] 到 #cf_span[n] 编号。因此，第 #cf_span[i] 台被黑的计算机位于坐标 #cf_span[xi] 处。此外，所有计算机的坐标互不相同。 Leha 希望在辛苦的一周后好好休息一下，因此他打算邀请朋友 Noora 去餐厅。然而，女孩同意约会的唯一条件是：Leha 必须解决一个简单的任务。 Leha 需要计算所有非空子集 #cf_span[a] 的 #cf_span[F(a)] 之和，其中 #cf_span[a] 是由所有被黑计算机组成的集合的子集。形式上，令 #cf_span[A] 表示从 #cf_span[1] 到 #cf_span[n] 的所有整数构成的集合。Noora 要求黑客求出表达式的值。这里 #cf_span[F(a)] 定义为集合 #cf_span[a] 中所有计算机对之间的最大距离。形式上，。由于所需总和可能很大，Noora 要求结果对 #cf_span[109 + 7] 取模。然而，Leha 太累了，无法解决这个任务。请帮助这位黑客赢得约会。第一行包含一个整数 #cf_span[n] #cf_span[(1 ≤ n ≤ 3·105)]，表示被黑计算机的数量。第二行包含 #cf_span[n] 个整数 #cf_span[x1, x2, ..., xn] #cf_span[(1 ≤ xi ≤ 109)]，表示被黑计算机的坐标。保证所有 #cf_span[xi] 互不相同。请输出一个整数——所需总和对 #cf_span[109 + 7] 取模的结果。在第一个样例测试中，有三个非空子集：, 和。第一个和第二个子集对总和的贡献为 #cf_span[0]，第三个子集对总和的贡献为 #cf_span[7 - 4 = 3]。因此总答案为 #cf_span[0 + 0 + 3 = 3]。在第二个样例测试中，有七个非空子集。其中只有以下子集对答案有贡献：, , , 。总和为 #cf_span[(4 - 3) + (4 - 1) + (3 - 1) + (4 - 1) = 9]。 ## Input 第一行包含一个整数 #cf_span[n] #cf_span[(1 ≤ n ≤ 3·105)]，表示被黑计算机的数量。第二行包含 #cf_span[n] 个整数 #cf_span[x1, x2, ..., xn] #cf_span[(1 ≤ xi ≤ 109)]，表示被黑计算机的坐标。保证所有 #cf_span[xi] 互不相同。 ## Output 请输出一个整数——所需总和对 #cf_span[109 + 7] 取模的结果。 [samples] ## Note 在第一个样例测试中，有三个非空子集：, 和。第一个和第二个子集对总和的贡献为 #cf_span[0]，第三个子集对总和的贡献为 #cf_span[7 - 4 = 3]。因此总答案为 #cf_span[0 + 0 + 3 = 3]。在第二个样例测试中，有七个非空子集。其中只有以下子集对答案有贡献：, , , 。总和为 #cf_span[(4 - 3) + (4 - 1) + (3 - 1) + (4 - 1) = 9]。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of hacked computers. Let $ X = \{x_1, x_2, \dots, x_n\} \subset \mathbb{R} $ be the set of distinct coordinates of the computers, with $ x_1 < x_2 < \dots < x_n $ after sorting. Let $ \mathcal{P}(X) \setminus \{\emptyset\} $ be the set of all non-empty subsets of $ X $. For a non-empty subset $ a \subseteq X $, define: $$ F(a) = \max_{p,q \in a} |p - q| = \max(a) - \min(a) $$ **Constraints** 1. $ 1 \le n \le 3 \cdot 10^5 $ 2. $ 1 \le x_i \le 10^9 $ for all $ i $, and all $ x_i $ are distinct. **Objective** Compute: $$ \sum_{\substack{a \subseteq X \\ a \ne \emptyset}} F(a) \mod (10^9 + 7) $$

Samples

Input #1

2
4 7

Output #1

Input #2

3
4 3 1

Output #2

API Response (JSON)

{
  "problem": {
    "name": "C. Do you want a date?",
    "description": {
      "content": "Leha decided to move to a quiet town Vičkopolis, because he was tired by living in Bankopolis. Upon arrival he immediately began to expand his network of hacked computers. During the week Leha managed",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF810C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Leha decided to move to a quiet town Vičkopolis, because he was tired by living in Bankopolis. Upon arrival he immediately began to expand his network of hacked computers. During the week Leha managed...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Leha 决定搬到宁静的小镇 Vičkopolis，因为他厌倦了在 Bankopolis 的生活。到达后，他立即开始扩展自己黑入的计算机网络。在一周内，Leha 成功获取了小镇上 #cf_span[n] 台计算机的访问权限。巧合的是，所有被 Leha 黑入的计算机都位于同一条直线上，这是因为 Vičkopolis 只有一条笔直的街道。\n\n让我们在这条街上建立一个坐标系，并将所有被黑的计算机从 #c...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of hacked computers.  \nLet $ X = \\{x_1, x_2, \\dots, x_n\\} \\subset \\mathbb{R} $ be the set of distinct coordinates of the computers, with $ x_...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments