Moving Dots

题意翻译

定义 $f(S)$ 为 $S$ 中 每个点按照同一速度向距离他最近的点的方向移动，如果两边相等，则走左边。当所有点停下之后的不同坐标个数。 给定点全集 $S$ ，求 $ \sum\limits_{T\in S,|T|>1}f(T)$。 $n=|S|\leq 3000$。

题目描述

We play a game with $ n $ dots on a number line. The initial coordinate of the $ i $ -th dot is $ x_i $ . These coordinates are distinct. Every dot starts moving simultaneously with the same constant speed. Each dot moves in the direction of the closest dot (different from itself) until it meets another dot. In the case of a tie, it goes to the left. Two dots meet if they are in the same coordinate, after that, they stop moving. After enough time, every dot stops moving. The result of a game is the number of distinct coordinates where the dots stop. Because this game is too easy, calculate the sum of results when we play the game for every subset of the given $ n $ dots that has at least two dots. As the result can be very large, print the sum modulo $ 10^9+7 $ .

输入输出格式

输入格式

The first line contains one integer $ n $ ( $ 2 \leq n \leq 3000 $ ). The next line contains $ n $ integers $ x_1, x_2, \ldots, x_n $ ( $ 1 \leq x_1 < x_2 < \ldots < x_n \leq 10^9 $ ), where $ x_i $ represents the initial coordinate of $ i $ -th dot.

输出格式

Print the sum of results modulo $ 10^9+7 $ .

输入输出样例

输入样例 #1

4
1 2 4 6

输出样例 #1

11

输入样例 #2

5
1 3 5 11 15

输出样例 #2

30

说明

In the first example, for a subset of size $ 2 $ , two dots move toward each other, so there is $ 1 $ coordinate where the dots stop. For a subset of size $ 3 $ , the first dot and third dot move toward the second dot, so there is $ 1 $ coordinate where the dots stop no matter the direction where the second dot moves. For $ [1, 2, 4, 6] $ , the first and second dots move toward each other. For the third dot, initially, the second dot and the fourth dot are the closest dots. Since it is a tie, the third dot moves left. The fourth dot also moves left. So there is $ 1 $ coordinate where the dots stop, which is $ 1.5 $ . Because there are $ 6 $ subsets of size $ 2 $ , $ 4 $ subsets of size $ 3 $ and one subset of size $ 4 $ , the answer is $ 6 \cdot 1 + 4 \cdot 1 + 1 = 11 $ . In the second example, for a subset of size $ 5 $ (when there are dots at $ 1 $ , $ 3 $ , $ 5 $ , $ 11 $ , $ 15 $ ), dots at $ 1 $ and $ 11 $ will move right and dots at $ 3 $ , $ 5 $ , $ 15 $ will move left. Dots at $ 1 $ , $ 3 $ , $ 5 $ will eventually meet at $ 2 $ , and dots at $ 11 $ and $ 15 $ will meet at $ 13 $ , so there are $ 2 $ coordinates where the dots stop.

**题目大意**：

定义函数 $ f(S) $ 为集合 $ S $ 中每个点以相同速度向距离它最近的点移动的方向，如果有两边距离相等，则选择向左移动。当所有点停止移动后，计算停止点坐标的不同个数。

给定一个点集合 $ S $，求所有 $ T \in S $ 且 $ |T| > 1 $ 的 $ f(T) $ 之和。

其中 $ n = |S| \leq 3000 $。

**输入输出格式**：

- **输入格式**：
- 第一行包含一个整数 $ n $（$ 2 \leq n \leq 3000 $）。
- 下一行包含 $ n $ 个整数 $ x_1, x_2, \ldots, x_n $（$ 1 \leq x_1 < x_2 < \ldots < x_n \leq 10^9 $），其中 $ x_i $ 表示第 $ i $ 个点的初始坐标。

- **输出格式**：
- 输出结果模 $ 10^9+7 $ 的值。

**输入输出样例**：

- **输入样例 #1**：
```
4
1 2 4 6
```
- **输出样例 #1**：
```
11
```

- **输入样例 #2**：
```
5
1 3 5 11 15
```
- **输出样例 #2**：
```
30
```

**说明**：

在第一个例子中，对于大小为 2 的子集，两个点相互向对方移动，因此有一个坐标点停止。对于大小为 3 的子集，第一个点和第三个点向第二个点移动，所以无论第二个点向哪个方向移动，都只有一个坐标点停止。对于 [1, 2, 4, 6]，第一个和第二个点相互向对方移动。对于第三个点，最初，第二个点和第四个点是最接近的。由于距离相等，第三个点向左移动。第四个点也向左移动。所以有一个坐标点停止，即 1.5。

因为有 6 个大小为 2 的子集，4 个大小为 3 的子集和 1 个大小为 4 的子集，所以答案是 $ 6 \cdot 1 + 4 \cdot 1 + 1 = 11 $。

在第二个例子中，对于大小为 5 的子集（当有坐标点在 1, 3, 5, 11, 15 时），在 1 和 11 的点将向右移动，而在 3, 5, 15 的点将向左移动。在 1, 3, 5 的点最终会在 2 处相遇，而在 11 和 15 的点会在 13 处相遇，所以有两个坐标点停止。**题目大意**： 定义函数 $ f(S) $ 为集合 $ S $ 中每个点以相同速度向距离它最近的点移动的方向，如果有两边距离相等，则选择向左移动。当所有点停止移动后，计算停止点坐标的不同个数。 给定一个点集合 $ S $，求所有 $ T \in S $ 且 $ |T| > 1 $ 的 $ f(T) $ 之和。 其中 $ n = |S| \leq 3000 $。 **输入输出格式**： - **输入格式**： - 第一行包含一个整数 $ n $（$ 2 \leq n \leq 3000 $）。 - 下一行包含 $ n $ 个整数 $ x_1, x_2, \ldots, x_n $（$ 1 \leq x_1 < x_2 < \ldots < x_n \leq 10^9 $），其中 $ x_i $ 表示第 $ i $ 个点的初始坐标。 - **输出格式**： - 输出结果模 $ 10^9+7 $ 的值。 **输入输出样例**： - **输入样例 #1**： ``` 4 1 2 4 6 ``` - **输出样例 #1**： ``` 11 ``` - **输入样例 #2**： ``` 5 1 3 5 11 15 ``` - **输出样例 #2**： ``` 30 ``` **说明**： 在第一个例子中，对于大小为 2 的子集，两个点相互向对方移动，因此有一个坐标点停止。对于大小为 3 的子集，第一个点和第三个点向第二个点移动，所以无论第二个点向哪个方向移动，都只有一个坐标点停止。对于 [1, 2, 4, 6]，第一个和第二个点相互向对方移动。对于第三个点，最初，第二个点和第四个点是最接近的。由于距离相等，第三个点向左移动。第四个点也向左移动。所以有一个坐标点停止，即 1.5。 因为有 6 个大小为 2 的子集，4 个大小为 3 的子集和 1 个大小为 4 的子集，所以答案是 $ 6 \cdot 1 + 4 \cdot 1 + 1 = 11 $。 在第二个例子中，对于大小为 5 的子集（当有坐标点在 1, 3, 5, 11, 15 时），在 1 和 11 的点将向右移动，而在 3, 5, 15 的点将向左移动。在 1, 3, 5 的点最终会在 2 处相遇，而在 11 和 15 的点会在 13 处相遇，所以有两个坐标点停止。