B - Range Argmax Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 900 点

問題文

整数 N と整数の組が M 個与えられます． i 番目の組は (L_i,R_i) です．

以下の手順で生成されうる整数列 x=(x_1,x_2,\cdots,x_M) の個数を 998244353 で割った余りを求めて下さい．

  • (1,2,\cdots,N) の順列 p=(p_1,p_2,\cdots,p_N) を用意する．
  • 各 i (1 \leq i \leq M) について，p_{L_i},p_{L_i+1},\cdots,p_{R_i} の中で最も大きい値の index を x_i とする． つまり，\max(p_{L_i},p_{L_i+1},\cdots,p_{R_i})=p_{x_i} である．

制約

  • 2 \leq N \leq 300
  • 1 \leq M \leq N(N-1)/2
  • 1 \leq L_i < 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

3 2
1 2
1 3

出力例 1

4

例えば，p=(2,1,3) とした場合は x=(1,3) となります．

条件を満たす数列は，x=(1,1),(1,3),(2,2),(2,3) の 4 通りです．

入力例 2

6 3
1 2
3 4
5 6

出力例 2

8

入力例 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

Score : 900 points

Problem Statement

Given are an integer N and M pairs of integers. The i-th pair is (L_i,R_i).

Find the number of integer sequences x=(x_1,x_2,\cdots,x_M) that can be generated as follows, modulo 998244353.

  • Provide a permutation p=(p_1,p_2,\cdots,p_N) of (1,2,\cdots,N).
  • For each i (1 \leq i \leq M), let x_i be the index of the largest element among p_{L_i},p_{L_i+1},\cdots,p_{R_i}. That is, \max(p_{L_i},p_{L_i+1},\cdots,p_{R_i})=p_{x_i}.

Constraints

  • 2 \leq N \leq 300
  • 1 \leq M \leq N(N-1)/2
  • 1 \leq L_i < R_i \leq N
  • (L_i,R_i) \neq (L_j,R_j) (i \neq j)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
L_1 R_1
L_2 R_2
\vdots
L_M R_M

Output

Print the answer.

Sample Input 1

3 2
1 2
1 3

Sample Output 1

4

For example, for p=(2,1,3), we will have x=(1,3).

The four sequences that meet the requirement are x=(1,1),(1,3),(2,2),(2,3).

Sample Input 2

6 3
1 2
3 4
5 6

Sample Output 2

8

Sample Input 3

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

Sample Output 3

1060