Score : $600$ points

问题陈述

存在一棵具有 $N$ 个顶点的有根树，顶点依次标记为 Vertex $1$, $2$, $\ldots$, $N$，且以 Vertex $1$ 为根。

我们从根节点出发执行了一次深度优先搜索，并得到了这棵树的前序遍历序列：$P_1, P_2, \ldots, P_N$。在搜索过程中，当当前顶点有多个子节点时，我们选择未访问过的索引最小的顶点。

什么是前序遍历？

我们从根节点开始，按照以下步骤重复操作来列出树的所有顶点：

• 如果当前顶点 $u$ 还未被记录，则记录它。
• 然后，如果 $u$ 有未访问过的子顶点，则移动到那个子顶点。
• 否则，如果 $u$ 是根节点，则结束遍历；如果不是，则返回到 $u$ 的父节点。

按照此处记录顺序得到的顶点列表即为该树的前序遍历。

找出与给定前序遍历相一致的根树的数量，结果对 $998244353$ 取模。

对于两棵具有 $N$ 个顶点且均以 Vertex $1$ 为根的根树，当这两棵树中存在至少一个非根顶点，其父节点在两棵树中不同，则认为这两棵树是不同的。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

There is a rooted tree with $N$ vertices called Vertex $1$, $2$, $\ldots$, $N$, rooted at Vertex $1$.

We performed a depth-first search starting at the root and obtained a preorder traversal of the tree: $P_1, P_2, \ldots, P_N$.
During the search, when the current vertex had multiple children, we chose the unvisited vertex with the smallest index.

What is a preorder traversal?

We start at the root and repeat the following procedure to list the vertices of the tree.- If the current vertex $u$ is not recorded yet, record it.

• Then, if $u$ has an unvisited vertex, go to that vertex.
• Otherwise, terminate if $u$ is the root, and go to the parent of $u$ if it is not. The list of vertices in the order they are recorded here is the preorder traversal of the tree.

Find the number of rooted trees consistent with the preorder traversal, modulo $998244353$.
Two rooted trees (with $N$ vertices and rooted at Vertex $1$) are considered different when there is a non-root vertex whose parent is different in the two trees.

Constraints

• $2 \leq N \leq 500$
• $1 \leq P_i\leq N$
• $P_1=1$
• All $P_i$ are distinct.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$

$P_1$ $P_2$ $\ldots$ $P_N$

Output

Print the number of rooted trees consistent with the preorder traversal, modulo $998244353$.

Sample Input 1

4
1 2 4 3

Sample Output 1

3

The rooted trees consistent with the preorder traversal are the three shown below, so the answer is $3$.

Note that the tree below does not count. This is because, among the children of Vertex $2$, we visit Vertex $3$ before visiting Vertex $4$, resulting in the preorder traversal $1,2,3,4$.

Sample Input 2

8
1 2 3 5 6 7 8 4

Sample Output 2

202

update @ 2024/3/10 10:46:26