← 返回题目列表

AtCoder · abc252_g

G. 预购

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

有一棵有根的树 N 名为 Vertex 的顶点 1, 2, \ldots, N,植根于 Vertex 1.

我们从根开始执行深度优先搜索,并获得树的前序遍历: P_1, P_2, \ldots, P_N.
在搜索过程中,当当前顶点有多个子节点时,我们选择索引最小的未访问顶点。

什么是前序遍历?
我们从根开始并重复以下过程来列出树的顶点。
  • 如果当前顶点 u 尚未记录,记录一下。
  • 那么,如果 u 有一个未访问的顶点,请转到该顶点。
  • 否则,终止如果 u 是根,转到父级 u 如果不是。
  • 这里记录的顶点列表就是树的前序遍历。

    求与前序遍历一致的有根树的数量,取模 998244353.
    两棵有根树( N 顶点并以 Vertex 为根 当两棵树中存在父节点不同的非根顶点时, 1) 被认为是不同的。

    约束

    • 2 \leq N \leq 500
    • 1 \leq P_i\leq N
    • P_1=1
    • 全部 P_i 是不同的。
    • 输入中的所有值都是整数。

    输入

    输入由标准输入按以下格式给出:

    N
    P_1 P_2 \ldots P_N
    

    输出

    打印与前序遍历一致的有根树的数量,取模 998244353.


    示例输入 1

    4
    1 2 4 3
    

    示例输出 1

    3
    

    与先序遍历一致的有根树是下图所示的三个,所以答案是 3.

    请注意,下面的树不算数。这是因为,Vertex 的孩子们中 2,我们访问Vertex 3 访问 Vertex 之前 4,导致先序遍历 1,2,3,4.


    示例输入 2

    8
    1 2 3 5 6 7 8 4
    

    示例输出 2

    202