← 返回题目列表

AtCoder · arc186_b

B. 典型排列描述符

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

分数: 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.