AT_arc113_f.[ARC113F] Social Distance

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个长度为 $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$ 取模输出。

期望值 $\bmod\ 998244353$ 的定义：可以证明所求的期望值一定是有理数。在本题的约束下，将其表示为最简分数 $\frac{P}{Q}$ 时， $Q \not\equiv 0 \pmod{998244353}$ 也成立。因此，存在唯一的整数 $R$ 满足 $R \times Q \equiv P \pmod{998244353},\ 0 \leq R < 998244353$ 。请输出这个 $R$ 。

输入格式

输入以如下格式从标准输入读入。

$N$ $X_0$ $X_1$ $\ldots$ $X_N$

输出格式

输出所有人之间的最小距离的期望值，对 $998244353$ 取模后的结果。

输入输出样例

输入#1
```
2
0 1 3
```
输出#1
```
499122178
```
输入#2
```
5
0 3 4 8 9 14
```
输出#2
```
324469854
```

输入#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

说明/提示

限制条件

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

样例解释 1

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

样例解释 2

答案是 $196249/172800$ 。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页