/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
長さ N+1 の整数列 X_0,X_1,\ldots,X_N が与えられます。 ここで、0=X_0 < X_1 < \ldots < X_N です。
これから、1 から N までの番号のついた N 人の人が、数直線上に現れます。 人 i は、区間 [X_{i-1},X_i] の中から一様ランダムに選ばれた実数座標に出現します。
人と人の距離の最小値の期待値を \bmod 998244353 で求めてください。
期待値 \bmod 998244353 の定義
求める期待値は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、その値を既約分数 \frac{P}{Q} で表した時、Q \neq 0 \pmod{998244353} となることも証明できます。 よって、R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353 を満たす整数 R が一意に定まります。 この 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
出力
人と人の距離の最小値の期待値を \bmod 998244353 で出力せよ。
入力例 1
2 0 1 3
出力例 1
499122178
人が二人しかいないので、人と人の距離の最小値の期待値は、人 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
Score : 1000 points
Problem Statement
Given is an integer sequence of length N+1: X_0,X_1,\ldots,X_N, where 0=X_0 < X_1 < \ldots < X_N holds.
Now, N people numbered 1 through N will appear on a number line. Person i will appear at a real coordinate chosen uniformly at random from the interval [X_{i-1},X_i].
Find the expected value of the smallest distance between two people, modulo 998244353.
Definition of the expected value modulo 998244353
We can prove that the expected value in question is always a rational number. We can also prove that, under the constraints of this problem, if we express the expected value as an irreducible fraction \frac{P}{Q}, we have Q \neq 0 \pmod{998244353}. Thus, there uniquely exists an integer R such that R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353. Report this R.
Constraints
- 2 \leq N \leq 20
- 0=X_0 < X_1 < \cdots < X_N \leq 10^6
Input
Input is given from Standard Input in the following format:
N X_0 X_1 \ldots X_N
Output
Print the expected value of the smallest distance between two people, modulo 998244353.
Sample Input 1
2 0 1 3
Sample Output 1
499122178
There are just two people, so the expected value of the smallest distance between two people is just the expected value of the distance between Person 1 and Person 2. The answer is 3/2.
Sample Input 2
5 0 3 4 8 9 14
Sample Output 2
324469854
The answer is 196249/172800.
Sample Input 3
20 0 38927 83112 125409 165053 204085 246405 285073 325658 364254 406395 446145 485206 525532 563762 605769 644863 683453 722061 760345 798556
Sample Output 3
29493181