← 返回题目列表

AtCoder · arc113_f

F. 社交距离

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

分数: 1000 点

问题陈述

给定的是长度的整数序列 N+1: X_0,X_1,\ldots,X_N,其中 0=X_0 < X_1 < \ldots < X_N 成立。

现在, N 人数 1 通过 N 将出现在数轴上。 人 i 将出现在 真实 从区间中均匀随机选择的坐标 [X_{i-1},X_i].

求两个人之间最小距离的期望值,取模 998244353.

期望值模的定义 998244353

我们可以证明所讨论的期望值始终是有理数。 我们还可以证明,在这个问题的约束下,如果我们将期望值表示为不可约分数 \frac{P}{Q},我们有 Q \neq 0 \pmod{998244353}。 因此,唯一存在一个整数 R 这样 R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353。 报告此事 R.

约束

  • 2 \leq N \leq 20
  • 0=X_0 < X_1 < \cdots < X_N \leq 10^6

输入

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

N
X_0 X_1 \ldots X_N

输出

打印两个人之间最小距离的期望值,取模 998244353.


样本输入 1

2
0 1 3

示例输出 1

499122178

只有两个人,所以两个人之间的最小距离的期望值就是Person之间的距离的期望值 1 和人 2。 答案是 3/2.


示例输入 2

5
0 3 4 8 9 14

示例输出 2

324469854

答案是 196249/172800.


示例输入 3

20
0 38927 83112 125409 165053 204085 246405 285073 325658 364254 406395 446145 485206 525532 563762 605769 644863 683453 722061 760345 798556

示例输出 3

29493181