题目描述
長さ N+1 の整数列 X0,X1,…,XN が与えられます。 ここで、0=X0 < X1 < … < XN です。
これから、1 から N までの番号のついた N 人の人が、数直線上に現れます。 人 i は、区間 [Xi−1,Xi] の中から一様ランダムに選ばれた実数座標に出現します。
人と人の距離の最小値の期待値を mod 998244353 で求めてください。
期待値 mod 998244353 の定義 求める期待値は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、その値を既約分数 QP で表した時、Q = 0 (mod998244353) となることも証明できます。 よって、$ R\ \times\ Q\ \equiv\ P\ \pmod{998244353},\ 0\ \leq\ R\ <\ 998244353 $ を満たす整数 R が一意に定まります。 この R を答えてください。
输入格式
入力は以下の形式で標準入力から与えられる。
N X0 X1 … XN
输出格式
人と人の距離の最小値の期待値を mod 998244353 で出力せよ。
题目大意
- 给定一个长为 n 的递增序列 x0,x1,⋯,xn,其中 x0=0。
- 对于每个 1≤i≤n 的 i,在 [xi−1,xi] 中随机选取一个实数作为 ai。
- 求 min2≤i≤nai−ai−1 的期望,答案对 998244353 取模。
- 2≤n≤20,xn≤106。
2
0 1 3
499122178
5
0 3 4 8 9 14
324469854
20
0 38927 83112 125409 165053 204085 246405 285073 325658 364254 406395 446145 485206 525532 563762 605769 644863 683453 722061 760345 798556
29493181
提示
制約
- 2 ≤ N ≤ 20
- 0=X0 < X1 < ⋯ < XN ≤ 106
Sample Explanation 1
人が二人しかいないので、人と人の距離の最小値の期待値は、人 1 と人 2 の距離の期待値と同じです。 答えは 3/2 です。
Sample Explanation 2
答えは 196249/172800 です。