当前没有测试数据。

H - 随机的第K大值

得分：$600$ 分

问题描述

我们有 $N$ 个连续随机变量 $X_1,X_2,\dots,X_N$。$X_i$ 在区间 $\lbrack L_i, R_i \rbrack$ 上有一个连续均匀分布。
设 $E$ 为 $N$ 个随机变量中第 $K$ 大的值的期望值。按照注释中的要求，将 $E \bmod {998244353}$ 输出。

注释

在这个问题中，我们可以证明 $E$ 总是一个有理数。此外，问题的约束保证，当 $E$ 表示为一个不可约分数 $\frac{y}{x}$ 时，$x$ 不可被 $998244353$ 整除。
在这里，一定存在一个整数 $z$，满足 $xz \equiv y \pmod{998244353}$，并且 $z$ 在 $0$ 到 $998244352$ 之间。输出这个 $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
0 2

1

答案是在区间 $\lbrack 0, 2 \rbrack$ 上有一个连续均匀分布的随机变量的期望值。因此，我们应该输出 $1$。

2 2
0 2
1 3

707089751

答案表示为一个不可约分数是 $\frac{23}{24}$。我们有 $707089751 \times 24 \equiv 23 \pmod{998244353}$，所以我们应该输出 $707089751$。

10 5
35 48
44 64
47 59
39 97
36 37
4 91
38 82
20 84
38 50
39 69

810056397