C - Topological Sort
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : {100} 点
問題文
(1,2,\ldots,N) の順列を以下では単に順列と呼びます。
正整数 N と順列 P が与えられます。
有向閉路と多重辺を持たない、頂点に 1 から N までの番号が付けられ、辺に番号が付けられていない N 頂点の有向グラフであって、辞書順最小トポロジカル順序が P と一致するようなものの個数を 998244353 で割った余りを求めてください。
辞書順最小トポロジカル順序の定義
順列 Q と(頂点に 1 から N までの番号が付けられている)N 頂点の有向グラフ G が以下の条件を満たすとき、 Q は G のトポロジカル順序であると言います。
- G の各有向辺 e=(u,v) ( u が始点、 v が終点)に対して、 u は Q において v よりも先に現れる
制約
- 2\leq N\leq 2\times 10^5
- (P_1, P_2, \ldots,P_N) は (1,2, \ldots,N) の順列
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N P_1 P_2 \ldots P_N
出力
答えを出力せよ。
入力例1
3 1 3 2
出力例1
4
以下の 4 つの有向グラフが条件を満たします。
入力例2
5 1 2 3 4 5
出力例2
1024
入力例3
6 4 2 1 5 6 3
出力例3
4096