CF1788D Moving Dots

我们在数轴上玩一个有 $n$ 个点的游戏。 第 $i$ 个点的初始坐标为 $x_i$。这些坐标互不相同。每个点同时以相同的恒定速度开始移动。 每个点会朝着距离自己最近的另一个点的方向移动，直到遇到另一个点为止。在距离相等的情况下，点会向左移动。当两个点在同一坐标时相遇，之后它们就会停止移动。 经过足够长的时间后，每个点都会停止移动。游戏的结果是所有点最终停止时所在的不同坐标的数量。 由于这个游戏太简单了，请你计算对于所有至少包含两个点的点集，游戏结果的总和。由于结果可能很大，请输出结果对 $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$ 取模后的值。

在第一个样例中，对于大小为 $2$ 的子集，两个点会相向而行，因此最终只有 $1$ 个坐标。 对于大小为 $3$ 的子集，第一个点和第三个点会朝着第二个点移动，因此无论第二个点向哪个方向移动，最终都只有 $1$ 个坐标。 对于 $[1, 2, 4, 6]$，第一个点和第二个点会相向而行。对于第三个点，最初第二个点和第四个点距离相等，由于平局，第三个点会向左移动。第四个点也会向左移动。因此最终只有 $1$ 个坐标，即 $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$ 处相遇，因此最终有 $2$ 个坐标。 由 ChatGPT 4.1 翻译