← 返回题目列表

AtCoder · dwacon6th_prelims_b

B. 融合史莱姆

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

分数: 600 点

问题陈述

有 N 史莱姆站在数轴上。 的 i左边第一个史莱姆位于位置 x_i.

保证 1 \leq x_1 < x_2 < \ldots < x_N \leq 10^{9}.

Niwango 将表演 N-1 操作。 i第次操作由以下过程组成:

  • 选择一个整数 k 之间 1 和 N-i (含)等概率。
  • 移动 k从左侧开始的第一个史莱姆,到右侧相邻史莱姆的位置。
  • 将同一位置的两个史莱姆融合成一个史莱姆。

求史莱姆移动的总距离乘以 (N-1)! (我们可以证明这个值是一个整数),模 (10^{9}+7)。如果史莱姆是通过导火线诞生的,并且该史莱姆会移动,我们将其视为一个史莱姆。

约束

  • 2 \leq N \leq 10^{5}
  • 1 \leq x_1 < x_2 < \ldots < x_N \leq 10^{9}
  • x_i 是一个整数。

子任务

  • 400 通过满足以下条件的测试用例将获得积分 N \leq 2000.

输入

输入由标准输入按以下格式给出:

N
x_1 x_2 \ldots x_N

输出

打印答案。


示例输入 1

3
1 2 3

示例输出 1

5
  • 有概率 \frac{1}{2},在第一次操作中选择最左边的史莱姆,在这种情况下,移动的总距离为 2.
  • 有概率 \frac{1}{2},在第一次操作中选择中间的史莱姆,在这种情况下,移动的总距离为 3.
  • 答案是预期的总行驶距离, 2.5,乘以 2!,即 5.

示例输入 2

12
161735902 211047202 430302156 450968417 628894325 707723857 731963982 822804784 880895728 923078537 971407775 982631932

示例输出 2

750927044
  • 求期望值乘以 (N-1)!,模数 (10^9+7).