← 返回题目列表

AtCoder · arc178_d

D. 删除范围 Mex

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

分数: 700 点

问题陈述

给你一个正整数 N 和一系列 M 非负整数 A = (A_{1}, A_{2}, \dots, A_{M}).

这里,所有元素 A 是之间不同的整数 0 和 N-1,包括在内。

求模数 998244353,排列 P of (0, 1, \dots, N-1) 满足以下条件。

  • 初始化序列后 B = (B_{1}, B_{2}, \dots, B_{N}) to P,可以使 B = A 通过重复以下操作一定次数:
    • 选择 l 和 r 这样 1 \leq l \leq r \leq |B|,如果 \mathrm{mex}(\{B_{l}, B_{l+1}, \dots, B_{r}\}) 包含在 B,将其从 B.
什么是 \mathrm{mex}(X)? 对于有限集 X 非负整数, \mathrm{mex}(X) 被定义为不在其中的最小非负整数 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),删除 \mathrm{mex}(\{1, 0, 3\}) = 2 来自 B, 制作 B = (1, 0, 3).
  • 选择 (l, r) = (3, 3),删除 \mathrm{mex}(\{3\}) = 0 来自 B, 制作 B = (1, 3).

因此, P = (2, 1, 0, 3) 满足条件。

有八种排列 P 满足条件,包括以上,所以打印 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.