Short Colorful Strip
Contest: Codeforces Global Round 4
Difficulty rating: 2200
Tags: combinatorics, dfs and similar, dp

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$$$.

Input format:
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 format:
Output a single integer — the number of ways Alice can perform the painting, modulo $$$998244353$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
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$$$.

Example input:
3 3
1 2 3

Example output:
5

Example input:
7 7
4 5 1 6 2 3 7

Example output:
165

Editorial:
Let $$$LO[l][r]$$$ be the lowest ID of a colour used in the final strip on interval $$$[l,r]$$$. Let $$$I[c]$$$ be the position on which the colour $$$c$$$ occurs on the target strip.
We solve this problem by computing $$$DP[l][r]$$$ – the number of ways of painting the interval $$$[l,r]$$$, given that it is painted with a single colour and all subsequent colouring intervals must be either completely inside or completely outside of this interval.

The first colour used on this interval will be $$$c = LO[l][r]$$$. How can we choose to paint it? Clearly, we can choose any interval $$$[a,b]$$$ such that $$$l \leq a \leq I[c] \leq b \leq r$$$. Once we perform this operation, then $$$I[c]$$$ can never be recoloured, and the interval $$$[l,r]$$$ is split into four single coloured intervals (possibly empty) that can be solved independently.

This gives us $$$DP[l][r] = \sum_a \sum_b DP[l][a-1] * DP[a][I[c]-1] * DP[I[c]+1][b] * DP[b+1][r]$$$ which can be computed naively in $$$\mathcal O(n^4)$$$. To optimise it to $$$\mathcal O(n^3)$$$ just note that the selection of $$$a$$$ and $$$b$$$ is independent.