分数: 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