G - Pre-Order Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

頂点 1 を根とした N 頂点の根付き木があります。頂点には 1,2,\ldots,N の番号がついています。

根から始めて深さ優先探索を行い、行きがけ順で頂点番号を記録したところ、順に P_1,P_2,\ldots,P_N となりました。
ただし、深さ優先探索では、現在の頂点に複数の子がある場合、まだ探索していない頂点のうち最も番号が小さい頂点へ移動することとします。

行きがけ順とは
根から始めて次の手順を繰り返して根付き木上の頂点を列挙します。
  • 現在いる頂点 u をまだ記録していなければ記録する。
  • その後、u の子のうち、まだ探索していないものがあればその頂点に移動する。
  • そうでない時、u が根であれば探索を終了する。そうでなければ、u の親に移動する。
    • この時、列挙された頂点を順に並べたものが行きがけ順です。

    条件をみたす根付き木として考えられるものの数を 998244353 で割った余りを求めてください。
    ただし、ある 2 つの「頂点 1 を根とした N 頂点の根付き木」が異なるとは、ある根以外の頂点が存在して、その親が異なる事を言います。

    制約

    • 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 通りが考えられます。よって、 3 を出力します。

    また、次のような木は考えられません。頂点 2 の子の頂点のうち、番号の小さい頂点 3 が頂点 4 より先に探索され、 このときの行きがけ順は 1,2,3,4 となるからです。

    入力例 2

    8
1 2 3 5 6 7 8 4

    出力例 2

    202

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