← 返回题目列表

AtCoder · awtf2025_b

B. 电影

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

分数: 1000 点

问题陈述

栗色的暑假持续了 N 从当天算起的天数 1 到白天 N。 放假期间, M 电影编号自 1 通过 M 预定上映,电影 i 可以从 Day 开始观看 L_i 到白天 R_i.

对于子集 s 所有电影,定义 f(s) 如下:

  • f(s) 是电影的最大数量 s 整个假期都可以观看,每天最多可以看一部电影。 在这里,多次观看同一部电影算作一部电影。

有 2^M 可能的设置 s。 求总和,取模 998244353,属于 f(s) 超过所有这些。

约束

  • 1 \leq N \leq 100
  • 1 \leq M \leq N \times (N+1) /2
  • 1 \leq L_i \leq R_i \leq N
  • (L_i,R_i) \neq (L_j,R_j) (i \neq j)
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
L_1 R_1
L_2 R_2
\vdots
L_M R_M

输出

输出答案。


示例输入 1

2 3
1 1
2 2
1 2

示例输出 1

11

f(s)=|s| 适用于大多数 s。 唯一的例外是 s=\{1,2,3\},其中 f(s)=2。 总和 f(s) 总的来说 s is 11.


示例输入 2

3 3
1 1
2 2
3 3

示例输出 2

12

示例输入 3

4 10
3 3
2 4
2 3
4 4
3 4
1 3
1 1
2 2
1 2
1 4

示例输出 3

3796

示例输入 4

7 20
1 3
4 5
3 3
3 5
1 4
4 7
2 3
1 7
6 7
4 6
2 4
6 6
3 6
2 5
7 7
3 4
2 2
5 5
2 6
1 2

示例输出 4

7113137