F - Count Permutations Many Times Editorial /

Time Limit: 6 sec / Memory Limit: 1024 MB

配点 : 800 点

問題文

長さ N の数列 A_0,A_1,\cdots,A_{N-1} があります。 次の Q 個の質問に答えてください。

  • 質問 i (0 \leq i \leq Q-1): 整数 L_i,R_i (0 \leq L_i < R_i \leq N) が与えられる。 (0,1,\cdots,N-1) の順列 p_0,p_1,\cdots,p_{N-1} であって、次の条件をみたすものの個数を求めよ。
    • 全ての j (L_i \leq j < R_i) について、p_j \neq A_j である。

ただし、答えは非常に大きくなることがあるので、998244353 で割ったあまりを出力してください。

制約

  • 1 \leq N \leq 2000
  • 0 \leq A_i \leq N-1
  • 1 \leq Q \leq 2000
  • 0 \leq L_i < R_i \leq N
  • 入力される値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

N Q
A_0 A_1 \cdots A_{N-1}
L_0 R_0
L_1 R_1
\vdots
L_{Q-1} R_{Q-1}

出力

Q 行出力せよ。 i+1 (0 \leq i \leq Q-1) 行目には、質問 i の答えを 998244353 で割ったあまりを出力せよ。

入力例 1

3 6
0 0 0
0 1
0 2
0 3
1 2
1 3
2 3

出力例 1

4
2
0
4
2
4

例えば質問 0 について考えると、条件をみたす順列は (1,0,2),(1,2,0),(2,0,1),(2,1,0) の 4 通りです。

入力例 2

3 6
0 1 2
0 1
0 2
0 3
1 2
1 3
2 3

出力例 2

4
3
2
4
3
4

入力例 3

10 10
7 9 4 8 0 6 7 8 9 8
0 5
4 7
3 10
7 10
7 9
4 9
0 3
6 9
4 9
1 3

出力例 3

2170680
2656080
1712520
2620800
2943360
2170680
2656080
2656080
2170680
2943360