← 返回题目列表

AtCoder · tupc2023_c

C. 拓扑排序

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

配点 : {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 出现在
G 之前且不存在有向环,则可以证明总存在这样一个排列是 G 的拓扑顺序,其中字典序最小的一个称为字典序最小的拓扑顺序。

制約

  • 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