← 返回题目列表

Codeforces · 1788/D

D. 移动点

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

我们玩一个在数轴上有 $$$n$$$ 个点的游戏。

第 $$$i$$$ 个点的初始坐标是 $$$x_i$$$。这些坐标是不同的。每个点开始以相同的恒定速度同时移动。

每个点都向最近的点(与其自身不同)的方向移动,直到遇到另一个点。如果是平局,它会向左移动。如果两个点在同一坐标上,它们就会相遇,之后它们就停止移动。

足够的时间后,每个点都停止移动。游戏的结果是点停止处的不同坐标的数量。

因为这个游戏太简单了,所以当我们玩游戏时,计算给定 $$$n$$$ 点的每个子集(至少有两个点)的结果总和。由于结果可能非常大,因此打印模 $$$10^9+7$$$ 的总和。

输入

第一行包含一个整数 $$$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$$$ 的子集,两个点向彼此移动,因此点停止的位置存在 $$$1$$$ 坐标。

对于 $$$3$$$ 大小的子集,第一个点和第三个点向第二个点移动,因此无论第二个点移动的方向如何,这些点停止的位置都有 $$$1$$$ 坐标。

对于 $$$[1, 2, 4, 6]$$$,第一个和第二个点朝彼此移动。对于第三点,最初,第二点和第四点是最接近的点。由于平局,第三个点向左移动。第四个点也向左移动。因此,点停止的位置有 $$$1$$$ 坐标,即 $$$1.5$$$。

因为存在 $$$6$$$ 大小为 $$$2$$$ 的子集、$$$4$$$ 大小为 $$$3$$$ 的子集以及一个大小为 $$$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$$$ 处相交,因此点停止处存在 $$$2$$$ 坐标。