← 返回题目列表

Codeforces · 1178/F1

F1. 短彩条

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

这是问题F的第一个子任务。这个子任务和第二个子任务之间的唯一区别是$$$m$$$的值的约束和时间限制。你需要解决这两个子任务才能破解这个任务。

宇宙中有$$$n+1$$$种不同的颜色,编号为$$$0$$$到$$$n$$$。有一条 $$$m$$$ 厘米长的纸条,最初涂有颜色 $$$0$$$。

Alice 拿起画笔并按照以下过程绘制了条带。对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$,按此顺序,她选择两个整数 $$$0 \leq a_i < b_i \leq m$$$,使得段 $$$[a_i, b_i]$$$ 当前使用单一颜色绘制,并用颜色 $$$i$$$ 重新绘制它。

Alice 选择这些片段的方式是,现在每一厘米都涂上 $$$0$$$ 以外的某种颜色。形式上,线段 $$$[i-1, i]$$$ 用颜色 $$$c_i$$$ ($$$c_i \neq 0$$$) 绘制。除了 $$$0$$$ 之外的所有颜色都在条上可见。

计算导致此配置的不同序列对 $$$\{a_i\}_{i=1}^n$$$、$$$\{b_i\}_{i=1}^n$$$ 的数量。

由于这个数字可能很大,因此输出它对 $$$998244353$$$ 取模。

输入

第一行包含两个整数 $$$n$$$, $$$m$$$ ($$$1 \leq n \leq 500$$$, $$$n = m$$$) - 分别是不包括颜色 $$$0$$$ 的颜色数和纸张长度。

第二行包含 $$$m$$$ 空格分隔的整数 $$$c_1, c_2, \ldots, c_m$$$ ($$$1 \leq c_i \leq n$$$) — 进程结束后 $$$[i-1, i]$$$ 段上可见的颜色。保证对于 $$$1$$$ 和 $$$n$$$ 之间的所有 $$$j$$$,存在一个索引 $$$k$$$,使得 $$$c_k = j$$$。

请注意,由于在此子任务 $$$n = m$$$ 中,这意味着 $$$c$$$ 是整数 $$$1$$$ 到 $$$n$$$ 的排列。

输出

输出一个整数 - Alice 可以执行绘画的方式数,以 $$$998244353$$$ 为模。

示例

输入 #1

3 3
1 2 3

输出 #1

5

输入 #2

7 7
4 5 1 6 2 3 7

输出 #2

165

注意

在第一个示例中,有 $$$5$$$ 种方式,全部如下图所示。这里,$$$0$$$ 是白色,$$$1$$$ 是红色,$$$2$$$ 是绿色,$$$3$$$ 是蓝色。

下面是无效绘制过程的示例,因为在第二步中,段 1 3 不是单色,因此不能用颜色 $$$2$$$ 重新绘制。