AT_abc226_h [ABC226H] Random Kth Max

题目描述

有 $N$ 个连续随机变量 $X_1, X_2, \dots, X_N$，其中 $X_i$ 服从区间 $[L_i, R_i]$ 上的连续均匀分布。
设 $E$ 为这 $N$ 个随机变量中第 $K$ 大的值的期望。如注记所述，请输出 $E \bmod 998244353$。

输入格式

输入通过标准输入给出，格式如下：

$N$ $K$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_N$ $R_N$

输出格式

输出 $E \bmod 998244353$。

输入输出样例 #1

输入 #1

1 1
0 2

输出 #1

1

输入输出样例 #2

输入 #2

2 2
0 2
1 3

输出 #2

707089751

输入输出样例 #3

输入 #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

说明/提示

注记

可以证明，本题中 $E$ 一定是一个有理数。此外，在本题的约束条件下，当 $E$ 表示为既约分数 $\frac{y}{x}$ 时，保证 $x$ 不被 $998244353$ 整除。
此时，存在唯一的整数 $z$（$0 \leq z \leq 998244352$）满足 $xz \equiv y \pmod{998244353}$。请将此 $z$ 作为 $E \bmod 998244353$ 输出。

约束条件

• $1 \leq N \leq 50$
• $1 \leq K \leq N$
• $0 \leq L_i < R_i \leq 100$
• 输入均为整数。

样例解释 #1

所求答案为服从区间 $[0, 2]$ 上的连续均匀分布的随机变量的期望值，因此输出 $1$。

样例解释 #2

答案可以表示为有理数 $\frac{23}{24}$。由于 $707089751 \times 24 \equiv 23 \pmod{998244353}$，因此输出 $707089751$。

翻译由 DeepSeek V3 完成