← 返回题目列表

AtCoder · abc226_h

H. 随机第 K 个最大值

中文机器翻译题面 查看原题

分数: 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