102267: [AtCoder]ABC226 H - Random Kth Max

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

问题描述

我们有$N$个连续随机变量$X_1,X_2,\dots,X_N$。$X_i$在区间$\lbrack L_i, R_i \rbrack$上具有连续均匀分布。
令$E$为这$N$个随机变量中第$K$大的值的期望值。按照Notes中的指定，打印$E \bmod {998244353}$。

注意

在这个问题中，我们可以证明$E$总是有理数。此外，本问题的约束条件保证，当$E$表示为不可约分数$\frac{y}{x}$时，$x$不能被$998244353$整除。
在这里，存在一个介于$0$和$998244352$之间的整数$z$，使得$xz \equiv y \pmod{998244353}$。打印这个$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