分数: 600 点
问题陈述
我们有 N 连续随机变量 X_1,X_2,\dots,X_N. X_i 在区间上具有连续均匀分布 \lbrack L_i, R_i \rbrack.
让 E 是预期值 K- 第一个最大的值 N 随机变量。打印 E \bmod {998244353} 如注释中指定。
注释
在这个问题中,我们可以证明 E 始终是有理数。此外,这个问题的约束保证,当 E 表示为不可约分数 \frac{y}{x}, x 不可整除 998244353.
这里,唯一存在一个整数 z 之间 0 和 998244352 这样 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