AT_abc252_g [ABC252G] Pre-Order

题目描述

有一棵以顶点 $1$ 为根的 $N$ 个顶点的有根树。顶点编号为 $1,2,\ldots,N$。

从根开始进行深度优先搜索（DFS），并按先序遍历记录顶点编号，得到顺序 $P_1,P_2,\ldots,P_N$。
在深度优先搜索中，如果当前顶点有多个未被访问的子节点，则总是优先访问编号最小的那个。

先序遍历的定义如下：从根开始，重复以下步骤，依次枚举有根树上的顶点。

1. 如果当前顶点 $u$ 尚未被记录，则记录它。
2. 然后，如果 $u$ 的子节点中还有未被访问的，则移动到编号最小的那个未访问的子节点。
3. 如果没有未访问的子节点，且 $u$ 是根，则遍历结束；否则返回到 $u$ 的父节点。
   按照上述顺序依次排列的顶点编号即为先序遍历序列。

请计算满足条件的有根树的方案数，并将结果对 $998244353$ 取模。
这里，若存在某个根以外的顶点，其父节点不同，则认为两棵“以顶点 $1$ 为根的 $N$ 个顶点的有根树”是不同的。

输入格式

输入以以下格式从标准输入读入。

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

输出格式

输出满足条件的有根树的方案数，对 $998244353$ 取模。

输入输出样例 #1

输入 #1

4
1 2 4 3

输出 #1

3

输入输出样例 #2

输入 #2

8
1 2 3 5 6 7 8 4

输出 #2

202

说明/提示

限制条件

• $2 \leq N \leq 500$
• $1 \leq P_i \leq N$
• $P_1 = 1$
• $P_i$ 互不相同
• 输入均为整数

样例解释 1

满足条件的有根树有如下 $3$ 种情况。因此，输出 $3$。

下图这样的树不满足条件。因为顶点 $2$ 的子节点中，编号较小的顶点 $3$ 会比顶点 $4$ 先被访问，此时先序遍历为 $1,2,3,4$。

由 ChatGPT 4.1 翻译