/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
N 個の連続確率変数 X_1,X_2,\dots,X_N があり、 X_i は \lbrack L_i, R_i \rbrack の範囲を取る連続一様分布に従います。
N 個の確率変数のうち大きい方から K 番目の値の期待値を E とします。注記に述べるように E \bmod {998244353} を出力してください。
注記
この問題で E は必ず有理数になることが証明できます。また、この問題の制約下では、E を既約分数 \frac{y}{x} で表したときに x が 998244353 で割り切れないことが保証されます。
このとき xz \equiv y \pmod{998244353} を満たすような 0 以上 998244352 以下の整数 z が一意に定まります。この z を E \bmod {998244353} として出力してください。
制約
- 1 \leq N \leq 50
- 1 \leq K \leq N
- 0 \leq L_i \lt R_i \leq 100
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N K L_1 R_1 L_2 R_2 \vdots L_N R_N
出力
E \bmod {998244353} を出力せよ。
入力例 1
1 1 0 2
出力例 1
1
\lbrack 0, 2 \rbrack 上の連続一様分布に従う確率変数の値の期待値が求める答えです。よって 1 を出力します。
入力例 2
2 2 0 2 1 3
出力例 2
707089751
答えを有理数で表すと \frac{23}{24} になります。707089751 \times 24 \equiv 23 \pmod{998244353} なので 707089751 を出力します。
入力例 3
10 5 35 48 44 64 47 59 39 97 36 37 4 91 38 82 20 84 38 50 39 69
出力例 3
810056397
Score : 600 points
Problem Statement
We have N continuous random variables X_1,X_2,\dots,X_N. X_i has a continuous uniform distribution over the interval \lbrack L_i, R_i \rbrack.
Let E be the expected value of the K-th greatest value among the N random variables. Print E \bmod {998244353} as specified in Notes.
Notes
In this problem, we can prove that E is always a rational number. Additionally, the Constraints of this problem guarantee that, when E is represented as an irreducible fraction \frac{y}{x}, x is indivisible by 998244353.
Here, there uniquely exists an integer z between 0 and 998244352 such that xz \equiv y \pmod{998244353}. Print this z as the value E \bmod {998244353}.
Constraints
- 1 \leq N \leq 50
- 1 \leq K \leq N
- 0 \leq L_i \lt R_i \leq 100
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K L_1 R_1 L_2 R_2 \vdots L_N R_N
Output
Print E \bmod {998244353}.
Sample Input 1
1 1 0 2
Sample Output 1
1
The answer is the expected value of the random variable with a continuous uniform distribution over the interval \lbrack 0, 2 \rbrack. Thus, we should print 1.
Sample Input 2
2 2 0 2 1 3
Sample Output 2
707089751
The answer represented as a rational number is \frac{23}{24}. We have 707089751 \times 24 \equiv 23 \pmod{998244353}, so we should print 707089751.
Sample Input 3
10 5 35 48 44 64 47 59 39 97 36 37 4 91 38 82 20 84 38 50 39 69
Sample Output 3
810056397