分数: 600 点
问题陈述
有 N 编号的方块 1 to N。最初,所有方块都漆成白色。
此外,还有 M 球编号 1 to M 在一个盒子里。
我们重复下面的过程,直到所有方块都被漆成黑色。
- 从盒子里随机均匀地捡起一个球。
- 让 x 是球的索引。油漆方块 L_x, L_x+1, \ldots, R_x 黑色。
- 将球放回盒子中。
求该过程完成次数的期望值,取模 998244353 (见注释)。
注释
可以证明,求的期望值始终是有理数。此外,在该问题的约束下,当该值表示为 \frac{P}{Q} 使用两个互质整数 P 和 Q,可以证明唯一存在一个整数 R 这样 R \times Q \equiv P\pmod{998244353} 和 0 \leq R \lt 998244353。你应该找到这个 R.
约束
- 1 \leq N,M \leq 400
- 1 \leq L_i \leq R_i \leq N
- 对于每个方格 i,有一个整数 j 这样 L_j \leq i \leq R_j.
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M
L_1 R_1
L_2 R_2
\hspace{0.5cm}\vdots
L_M R_M
输出
打印求模的期望值 998244353.
示例输入 1
3 3 1 1 1 2 2 3
示例输出 1
499122180
寻求的期望值为 \frac{7}{2}.
我们有 499122180 \times 2 \equiv 7\pmod{998244353},所以 499122180 。
示例输入 2
13 10 3 5 5 9 3 12 1 13 9 11 12 13 2 4 9 12 9 11 7 11
示例输出 2
10
示例输入 3
100 11 22 43 84 93 12 71 49 56 8 11 1 61 13 80 26 83 23 100 80 85 9 89
示例输出 3
499122193