#PQJ1032x5016. QOJ 1032_5016

    ID: 2529 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:2022-2023 集训队互测前缀和

QOJ 1032_5016

标题: Range Minimum Element - Problem - QOJ.ac

#5016. Range Minimum Element

Statistics

The problem was used in the following contests:

题目描述

有一个长度为 n,值域为 [1,c] 的正整数序列 a。给定 m 个区间 [li,ri],设长度为 m 的序列 b 满足 ∀i∈[1,m],bi=minj=liri{aj}。求出 a 在范围内任意取的情况下共能得到多少种不同的 b。答案对 998244353 取模。

输入格式

第一行,三个数,依次表示 n,m,c。

接下来 m 行,每行两个数 li,ri 表示一个给定的区间。

输出格式

共一行,一个数,表示答案。

样例数据

样例输入 1

3 2 2
1 2
2 3

样例输出 1

4

样例说明 1

当 a=(1,1,1) 时,b=(1,1)。

当 a=(1,1,2) 时,b=(1,1)。

当 a=(1,2,1) 时,b=(1,1)。

当 a=(1,2,2) 时,b=(1,2)。

当 a=(2,1,1) 时,b=(1,1)。

当 a=(2,1,2) 时,b=(1,1)。

当 a=(2,2,1) 时,b=(2,1)。

当 a=(2,2,2) 时,b=(2,2)。

因此共能得到 (1,1),(1,2),(2,1),(2,2) 这 4 种不同的 b。

样例输入 2

10 11 2
1 10
2 2
3 3
5 5
6 10
6 7
6 6
7 7
8 10
8 9
10 10

样例输出 2

129

样例说明 2

这个样例满足 Subtask⁡2∼7 的限制。

样例输入 3

40 40 40
31 34
9 34
4 25
36 38
8 29
8 30
6 26
17 19
6 23
36 39
11 39
2 10
32 37
32 33
33 35
17 21
8 35
31 40
11 25
11 20
8 37
26 36
22 34
17 39
28 38
26 28
11 12
12 15
12 37
1 9
11 23
5 26
8 11
1 23
12 32
7 19
22 28
20 27
8 40
19 40

样例输出 3

567581188

样例说明 3

这个样例满足 Subtask⁡5∼7 的限制。

数据范围

对于 100% 的数据, 1≤n≤100,1≤m≤n(n+1)2,1≤c<998244353,∀i∈[1,m],1≤li≤ri≤n 。保证给定的 m 个区间两两不同。

  • Subtask 1(5%): n,c≤5 。
  • Subtask 2(10%): c≤100 ,且对于任意两个有交的区间一定存在其中一个包含另一个。
  • Subtask 3(15%): m≤18,c=2 。
  • Subtask 4(20%): c=2 。
  • Subtask 5(15%): n,c≤40 。
  • Subtask 6(15%): c≤100 。
  • Subtask 7(20%): 无特殊限制。