G - Pre-Order
当前没有测试数据。
G - Pre-Order
Score : $600$ points
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.
<li> If the current vertex $u$ is not recorded yet, record it. </li> <li> Then, if $u$ has an unvisited vertex, go to that vertex.</li> <li> Otherwise, terminate if $u$ is the root, and go to the parent of $u$ if it is not. </li>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:
Output
Print the number of rooted trees consistent with the preorder traversal, modulo $998244353$.
4
1 2 4 3
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$.
8
1 2 3 5 6 7 8 4
202