Short Colorful Strip

题意翻译

#### 题目描述 这是F题的第一个子任务。F1和F2的区别仅在对于m和时间的限制上 有n+1种颜色标号从0到n，我们有一条全部染成颜色0的长为m的纸带。 Alice拿着刷子通过以下的过程来给纸带染色： 我们按照从1到n的顺序进行染色，进行每次染色时，我们选取一个区间[ai,bi]，0<=ai<bi<=m，并且这个区间内必定是单种颜色。 染色到最后，纸带上有各种颜色除了颜色0.给出纸带最终的状态，问有多少种不同的染色方案能到达最终状态。输出时结果模998244353。 #### 输入格式 第一行有两个整数n和m，1<=n<=500，并且保证m=n。n代表除了颜色0有多少种颜色，m代表纸带的长度。 第二行有m个用空格分隔的整数c1,c2,...,cm,(1<=ci<=n)，代表完成染色后纸带的最终状态。保证最终状态中能在纸带上找到从1到n所有的颜色。 注意，这个子任务保证了n=m，那么就是说最终状态是1到n的一个排列。 #### 输出格式 输入一个单独的整数，即Alice可行的染色方案数模998244353.

题目描述

This is the first subtask of problem F. The only differences between this and the second subtask are the constraints on the value of $ m $ and the time limit. You need to solve both subtasks in order to hack this one. There are $ n+1 $ distinct colours in the universe, numbered $ 0 $ through $ n $ . There is a strip of paper $ m $ centimetres long initially painted with colour $ 0 $ . Alice took a brush and painted the strip using the following process. For each $ i $ from $ 1 $ to $ n $ , in this order, she picks two integers $ 0 \leq a_i < b_i \leq m $ , such that the segment $ [a_i, b_i] $ is currently painted with a single colour, and repaints it with colour $ i $ . Alice chose the segments in such a way that each centimetre is now painted in some colour other than $ 0 $ . Formally, the segment $ [i-1, i] $ is painted with colour $ c_i $ ( $ c_i \neq 0 $ ). Every colour other than $ 0 $ is visible on the strip. Count the number of different pairs of sequences $ \{a_i\}_{i=1}^n $ , $ \{b_i\}_{i=1}^n $ that result in this configuration. Since this number may be large, output it modulo $ 998244353 $ .

输入输出格式

输入格式

The first line contains a two integers $ n $ , $ m $ ( $ 1 \leq n \leq 500 $ , $ n = m $ ) — the number of colours excluding the colour $ 0 $ and the length of the paper, respectively. The second line contains $ m $ space separated integers $ c_1, c_2, \ldots, c_m $ ( $ 1 \leq c_i \leq n $ ) — the colour visible on the segment $ [i-1, i] $ after the process ends. It is guaranteed that for all $ j $ between $ 1 $ and $ n $ there is an index $ k $ such that $ c_k = j $ . Note that since in this subtask $ n = m $ , this means that $ c $ is a permutation of integers $ 1 $ through $ n $ .

输出格式

Output a single integer — the number of ways Alice can perform the painting, modulo $ 998244353 $ .

输入输出样例

输入样例 #1

3 3
1 2 3

输出样例 #1

5

输入样例 #2

7 7
4 5 1 6 2 3 7

输出样例 #2

165

说明

In the first example, there are $ 5 $ ways, all depicted in the figure below. Here, $ 0 $ is white, $ 1 $ is red, $ 2 $ is green and $ 3 $ is blue.  Below is an example of a painting process that is not valid, as in the second step the segment 1 3 is not single colour, and thus may not be repainted with colour $ 2 $ . 

题意翻译

#### 题目描述 这是F题的第一个子任务。F1和F2的区别仅在对于m和时间的限制上 有n+1种颜色标号从0到n，我们有一条全部染成颜色0的长为m的纸带。 Alice拿着刷子通过以下的过程来给纸带染色： 我们按照从1到n的顺序进行染色，进行每次染色时，我们选取一个区间[ai,bi]，0<=ai<bi<=m，并且这个区间内必定是单种颜色。 染色到最后，纸带上有各种颜色除了颜色0.给出纸带最终的状态，问有多少种不同的染色方案能到达最终状态。输出时结果模998244353。 #### 输入格式 第一行有两个整数n和m，1<=n<=500，并且保证m=n。n代表除了颜色0有多少种颜色，m代表纸带的长度。 第二行有m个用空格分隔的整数c1,c2,...,cm,(1<=ci<=n)，代表完成染色后纸带的最终状态。保证最终状态中能在纸带上找到从1到n所有的颜色。 注意，这个子任务保证了n=m，那么就是说最终状态是1到n的一个排列。 #### 输出格式 输入一个单独的整数，即Alice可行的染色方案数模998244353.