分数: 900 点
问题陈述
给你一个整数序列 (A_1,\dots,A_N) 长度 N。该序列满足 0\le A_i < i 对于每个 i=1,\dots,N。 求排列数 (P_1,\dots,P_N) of (1,\dots,N) 满足以下条件,模 998244353.
- 对于每个 i=1,\dots,N:
- P_j > P_i 对于任何整数 j 与 A_i < j < i
- P_{A_i} < P_i if A_i > 0
对于序列 输入中给出的 (A_1,\dots,A_N) ,保证存在满足条件的排列。
约束
- 1\le N\le 3\times 10^5
- 0\le A_i \lt i
- 对于 A_1,\dots,A_N,存在满足问题陈述中的条件的排列。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \dots A_N
输出
打印满足条件的排列数,模 998244353.
示例输入 1
4 0 1 0 3
示例输出 1
3
存在三种这样的排列: (2, 3, 1, 4), (2, 4, 1, 3),和 (3, 4, 1, 2).
示例输入 2
22 0 1 2 2 2 2 2 2 1 9 9 9 9 0 14 15 15 15 14 19 19 19
示例输出 2
353820794
答案是 353820794,即 2350309500 模数 998244353.