/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 700 点
問題文
正整数 N と長さ M の非負整数列 A=(A_{1},A_{2},\dots, A_{M}) が与えられます。
ここで、 A の全ての要素は 0 以上 N 未満の整数で、相異なります。
(0, 1, \dots , N - 1) の順列 P のうち、以下の条件を満たすものの個数を 998244353 で割ったあまりを求めてください。
- 数列 B = (B_{1}, B_{2}, \dots , B_{N}) を P で初期化した後、以下の操作を好きな回数繰り返すことで B = A にすることができる。
- 1\leq l\leq r\leq |B| を満たす l,r を選び、 \mathrm{mex}(\{B_{l},B_{l+1},\dots ,B_{r}\}) が B に含まれているなら、それを B から削除する。
\mathrm{mex}(X) とは？
非負整数からなる有限集合 X に対し，x\notin X を満たす最小の非負整数 x を \mathrm{mex}(X) と定義します．制約
- 1\leq M\leq N\leq 500
- 0\leq A_{i}< N
- A の要素は互いに相異なる
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられます。
N M
A_{1} A_{2} \cdots A_{M}
出力
答えを出力してください。
入力例 1
4 2 1 3
出力例 1
8
B = (2, 1, 0, 3) で初期化したのち、以下の手順で B=A とすることが可能です。
- (l,r) = (2, 4) を選び、B から \mathrm{mex}(\{1,0,3\}) = 2 を削除し、B=(1,0,3) とする。
- (l,r) = (3, 3) を選び、B から \mathrm{mex}(\{3\}) = 0 を削除し、B=(1, 3) とする。
よって、P=(2, 1, 0, 3) は条件を満たします。
条件を満たす P はこれを含めて 8 通りあるので、8 を出力してください。
入力例 2
4 4 0 3 2 1
出力例 2
1
P = (0, 3, 2, 1) のときのみ条件を満たします。
入力例 3
16 7 9 2 4 0 1 6 7
出力例 3
3520
入力例 4
92 4 1 67 16 7
出力例 4
726870122
998244353 で割ったあまりを求めてください。
Score : 700 points
Problem Statement
You are given a positive integer N and a sequence of M non-negative integers A = (A_{1}, A_{2}, \dots, A_{M}).
Here, all elements of A are distinct integers between 0 and N-1, inclusive.
Find the number, modulo 998244353, of permutations P of (0, 1, \dots, N-1) that satisfy the following condition.
- After initializing a sequence B = (B_{1}, B_{2}, \dots, B_{N}) to P, it is possible to make B = A by repeating the following operation some number of times:
- Choose l and r such that 1 \leq l \leq r \leq |B|, and if \mathrm{mex}(\{B_{l}, B_{l+1}, \dots, B_{r}\}) is contained in B, remove it from B.
What is \mathrm{mex}(X)?
For a finite set X of non-negative integers, \mathrm{mex}(X) is defined as the smallest non-negative integer that is not in X.Constraints
- 1 \leq M \leq N \leq 500
- 0 \leq A_{i} < N
- All elements of A are distinct.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M
A_{1} A_{2} \cdots A_{M}
Output
Print the answer.
Sample Input 1
4 2 1 3
Sample Output 1
8
After initializing B = (2, 1, 0, 3), it is possible to make B = A using the following steps:
- Choose (l, r) = (2, 4), remove \mathrm{mex}(\{1, 0, 3\}) = 2 from B, making B = (1, 0, 3).
- Choose (l, r) = (3, 3), remove \mathrm{mex}(\{3\}) = 0 from B, making B = (1, 3).
Thus, P = (2, 1, 0, 3) satisfies the condition.
There are eight permutations P that satisfy the condition, including the above, so print 8.
Sample Input 2
4 4 0 3 2 1
Sample Output 2
1
Only P = (0, 3, 2, 1) satisfies the condition.
Sample Input 3
16 7 9 2 4 0 1 6 7
Sample Output 3
3520
Sample Input 4
92 4 1 67 16 7
Sample Output 4
726870122
Find the count modulo 998244353.