AT_arc186_b.[ARC186B] Typical Permutation Descriptor

给定一个长度为 $N$ 的整数序列 $(A_1,\dots,A_N)$。该整数序列满足对于每个 $i=1,\dots,N$，都有 $0\leq A_i < i$。请计算满足以下条件的 $(1,\dots,N)$ 的排列 $(P_1,\dots,P_N)$ 的个数，并对 $998244353$ 取模。

• 对于每个 $i=1,\dots,N$，
  • 对于所有满足 $A_i < j < i$ 的整数 $j$，都有 $P_j > P_i$。
  • 如果 $A_i > 0$，则 $P_{A_i} < P_i$。

保证对于输入给定的 $(A_1,\dots,A_N)$，一定存在满足条件的排列。

输入以以下格式从标准输入给出。

$N$ $A_1$ $A_2$ $\dots$ $A_N$

输出满足条件的排列数对 $998244353$ 取模的结果。

限制条件

• $1\leq N\leq 3\times 10^5$
• $0\leq A_i < i$
• 对于 $A_1,\dots,A_N$，保证存在满足题目条件的排列
• 输入均为整数

样例解释 1

满足条件的排列有 $(2,\ 3,\ 1,\ 4),\ (2,\ 4,\ 1,\ 3),\ (3,\ 4,\ 1,\ 2)$ 共 $3$ 个。

样例解释 2

$2350309500$ 对 $998244353$ 取模的结果为 $353820794$，即为答案。

由 ChatGPT 4.1 翻译