#P13073. [AGC056B] Range Argmax

    ID: 12257 传统题 2000ms 888MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2600省选/NOI-区间 DP计数 DP前缀和优化 DP双射计数

[AGC056B] Range Argmax

题目描述

给定一个整数 NN 和 MM 个整数对。第 ii 个整数对为 (Li,Ri)(L_i, R_i)。

请你求出,按照以下步骤可以生成的整数序列 x=(x1,x2,⋯ ,xM)x=(x_1, x_2, \cdots, x_M) 的种数,答案对 998244353998244353 取模。

  • 准备一个 11 到 NN 的排列 p=(p1,p2,⋯ ,pN)p=(p_1, p_2, \cdots, p_N)。
  • 对于每个 ii(1≤i≤M1 \leq i \leq M),令 xix_i 为 pLi,pLi+1,⋯ ,pRip_{L_i}, p_{L_i+1}, \cdots, p_{R_i} 中最大值的下标。即,$\max(p_{L_i}, p_{L_i+1}, \cdots, p_{R_i}) = p_{x_i}$。

输入格式

输入按以下格式从标准输入读入。

NN MM
L1L_1 R1R_1
L2L_2 R2R_2
⋮\vdots
LML_M RMR_M

输出格式

输出答案。

输入输出样例 #1

输入 #1

3 2
1 2
1 3

输出 #1

4

输入输出样例 #2

输入 #2

6 3
1 2
3 4
5 6

输出 #2

8

输入输出样例 #3

输入 #3

10 10
8 10
5 8
5 7
2 5
1 7
4 5
5 9
2 8
7 8
3 9

输出 #3

1060

说明/提示

限制条件

  • 2≤N≤3002 \leq N \leq 300
  • 1≤M≤N(N−1)21 \leq M \leq \dfrac{N(N-1)}{2}
  • 1≤Li<Ri≤N1 \leq L_i < R_i \leq N
  • (Li,Ri)≠(Lj,Rj)(L_i, R_i) \neq (L_j, R_j)(i≠ji \neq j)
  • 所有输入的值均为整数

样例解释 1

例如,当 p=(2,1,3)p=(2,1,3) 时,x=(1,3)x=(1,3)。满足条件的数列有 x=(1,1),(1,3),(2,2),(2,3)x=(1,1),(1,3),(2,2),(2,3) 共 44 种。