← 返回题目列表

AtCoder · jsc2019_final_f

F. 多次计算排列

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

配点 : 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