/
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 525 点
問題文
頂点 1, 頂点 2,\ldots, 頂点 N からなる N 頂点の木 T に対して、以下の手順で得られる (1,2,\ldots,N) の順列 P を f(T) とします。
- はじめ、列 P を空列 () とし、集合 S を \lbrace1\rbrace とする。
- 以下を N 回繰り返す。
- S の最小値を x とする。S から x を削除し、P の末尾に xを追加する。
- その後、T において頂点 x に隣接する頂点を頂点 v _ 1, 頂点 v _ 2,\ldots, 頂点 v _ k とする。i=1,2,\ldots,k について、P に v _ i が含まれていなければ S に v _ i を追加する。
(1,2,\ldots,N) の順列 Q=(Q _ 1,Q _ 2,\ldots,Q _ N) が与えられます。 f(T)=Q となる木 T の個数を 998244353 で割った余りを求めてください。 ただし、ふたつの木は、ある頂点の組 (u,v) が存在して、一方の木では頂点 u と頂点 v の間に辺があり、もう一方の木では辺がないとき、区別されます。
制約
- 1\le N\le2\times10 ^ 5
- 1\le Q _ i\le N\ (1\le i\le N)
- Q _ i\ne Q _ j\ (1\le i\lt j\le N)
- Q _ 1=1
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N Q _ 1 Q _ 2 \ldots Q _ N
出力
f(T)=Q となる木 T の個数を 998244353 で割った余りを出力せよ。
入力例 1
5 1 3 4 2 5
出力例 1
8
例えば、以下のような木を T とすると、f(T)=Q となります。

f(T) を求める手順は以下の図のように進行します。

この木を含めた以下の図のような 8 つの木が条件を満たします。

よって、8 を出力してください。
入力例 2
20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
出力例 2
868586527
条件を満たす木の個数を 998244353 で割った余りを出力してください。
入力例 3
30 1 16 23 14 18 10 12 21 27 30 17 28 4 9 20 13 22 11 19 3 25 26 6 7 2 8 5 24 15 29
出力例 3
910753763
Score : 525 points
Problem Statement
For a tree T with N vertices called vertex 1, vertex 2, \ldots, vertex N, let f(T) be the permutation P of (1,2,\ldots,N) obtained by the following procedure.
- Initially, let the sequence P be the empty sequence (), and let the set S be \lbrace1\rbrace.
- Repeat the following N times.
- Let x be the minimum value of S. Remove x from S, and append x to the end of P.
- Then, let v_1, v_2, \ldots, v_k be the vertices adjacent to vertex x in T. For i=1,2,\ldots,k, if v _ i is not contained in P, add v _ i to S.
You are given a permutation Q=(Q _ 1,Q _ 2,\ldots,Q _ N) of (1,2,\ldots,N). Find the number, modulo 998244353, of trees T such that f(T)=Q. Here, two trees are distinguished when there exists a pair of vertices (u,v) such that there is an edge between vertex u and vertex v in one tree and there is no edge in the other tree.
Constraints
- 1\le N\le2\times10 ^ 5
- 1\le Q _ i\le N\ (1\le i\le N)
- Q _ i\ne Q _ j\ (1\le i\lt j\le N)
- Q _ 1=1
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N Q _ 1 Q _ 2 \ldots Q _ N
Output
Output the number, modulo 998244353, of trees T such that f(T)=Q.
Sample Input 1
5 1 3 4 2 5
Sample Output 1
8
For example, if T is the following tree, then f(T)=Q.

The procedure to find f(T) proceeds as shown in the following figure.

Including this tree, the following eight trees satisfy the condition.

Thus, output 8.
Sample Input 2
20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Sample Output 2
868586527
Output modulo 998244353 the number of trees satisfying the condition.
Sample Input 3
30 1 16 23 14 18 10 12 21 27 30 17 28 4 9 20 13 22 11 19 3 25 26 6 7 2 8 5 24 15 29
Sample Output 3
910753763