← 返回题目列表

AtCoder · agc067_b

B. 修改

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

分数: 1100 点

问题陈述

你有一个整数序列 a=(a_1,a_2,\cdots,a_N) 长度 N。 所有元素最初都是 0.

给你一个整数 C 和 M 间隔 ([L_1,R_1],[L_2,R_2],\cdots,[L_M,R_M]).

您将选择一个排列 p of (1,2,\cdots,M) 和一个整数序列 w=(w_1,w_2,\cdots,w_M) 长度 M。 在这里, 1\le w_i\le C 必须保留。

然后,你会做 M 修改。 的 i-第修改如下:

  • 更改 a_{L_{p_i}}, \cdots, a_{R_{p_i}} to w_i.

保证每个位置 a 被至少一个区间覆盖。

找出可实现的数量 a 完成所有修改后。 打印答案取模 998244353.

约束

  • 1\le N\le 100
  • 1\le M\le\dfrac{N(N+1)}{2}
  • 1\le C<998244353
  • 1 \le L_i \le R_i \le N
  • (L_i,R_i) \neq (L_j,R_j) (i \neq j)
  • 中的每个位置 a 被至少一个区间覆盖。
  • 所有输入值均为整数。

输入

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

N M C
L_1 R_1
L_2 R_2
\vdots
L_M R_M

输出

打印答案。


示例输入 1

5 5 2
1 3
2 2
3 3
1 5
3 5

示例输出 1

16

有 16 可以实现的序列。 例如,您可以实现 a=(2,1,1,1,1) 按以下方式:

  • 选择 p=(4,1,2,3,5) 和 w=(1,2,1,2,1)
  • 的 1-st 操作更改 a 进入 (1,1,1,1,1)
  • 的 2-nd 操作更改 a 进入 (2,2,2,1,1)
  • 的 3-rd 操作更改 a 进入 (2,1,2,1,1)
  • 的 4-第操作更改 a 进入 (2,1,2,1,1)
  • 的 5-第操作更改 a 进入 (2,1,1,1,1)

示例输入 2

20 30 20
1 14
1 7
1 16
3 13
1 17
4 8
2 11
4 12
9 14
3 15
11 19
1 13
4 15
8 19
3 17
15 18
10 18
1 18
17 19
16 20
1 8
8 15
13 17
1 19
13 19
1 20
6 13
10 12
11 20
17 18

示例输出 2

258066445