AT_abc242_h [ABC242Ex] Random Painting

题目描述

有 $N$ 个编号为 $1$ 到 $N$ 的格子，开始时所有格子都是白色的。

同时，有 $M$ 个编号为 $1$ 到 $M$ 的球放在箱子里。

重复以下操作，直到所有 $N$ 个格子都被涂成黑色为止：

1. 从箱子中随机取出一个球。每个球被取出的概率相等。
2. 设取出的球的编号为 $x$，则将格子 $L_x, L_x+1, \ldots, R_x$ 全部涂成黑色。
3. 将取出的球放回箱子。

请计算将所有格子涂黑所需操作次数的期望值，并对 $998244353$ 取模输出（见注记）。

输入格式

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

$N$ $M$ $L_1$ $R_1$ $L_2$ $R_2$
$\hspace{0.5cm}\vdots$
$L_M$ $R_M$

输出格式

请输出所求期望值对 $998244353$ 取模的结果。

输入输出样例 #1

输入 #1

3 3
1 1
1 2
2 3

输出 #1

499122180

输入输出样例 #2

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

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

说明/提示

注记

可以证明，所求的期望值一定是有理数。在本题的约束下，若用互质的两个整数 $P$、$Q$ 表示为 $\frac{P}{Q}$，则一定存在唯一的整数 $R$ 满足 $R \times Q \equiv P \pmod{998244353}$ 且 $0 \leq R < 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$
• 所有输入均为整数

样例解释 1

所求期望值为 $\frac{7}{2}$。$499122180 \times 2 \equiv 7 \pmod{998244353}$，所以输出 $499122180$。

由 ChatGPT 4.1 翻译