/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 900 点
問題文
長さ N の整数列 (A_1,\dots,A_N) が与えられます。この整数列は、各 i=1,\dots,N について、0\le 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) について、条件を満たす順列が存在することが保証されます。
制約
- 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) の 3 つです。
入力例 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
2350309500 を 998244353 で割ったあまりである、 353820794 が答えです。
Score : 900 points
Problem Statement
You are given a sequence of integers (A_1,\dots,A_N) of length N. This sequence satisfies 0\le A_i < i for each i=1,\dots,N. Find the number of permutations (P_1,\dots,P_N) of (1,\dots,N) that satisfy the following conditions, modulo 998244353.
- For each i=1,\dots,N:
- P_j > P_i for any integer j with A_i < j < i
- P_{A_i} < P_i if A_i > 0
For the sequence (A_1,\dots,A_N) given in the input, it is guaranteed that there exists a permutation satisfying the conditions.
Constraints
- 1\le N\le 3\times 10^5
- 0\le A_i \lt i
- For A_1,\dots,A_N, there exists a permutation satisfying the conditions in the problem statement.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \dots A_N
Output
Print the number of permutations satisfying the conditions, modulo 998244353.
Sample Input 1
4 0 1 0 3
Sample Output 1
3
There are three such permutations: (2, 3, 1, 4), (2, 4, 1, 3), and (3, 4, 1, 2).
Sample Input 2
22 0 1 2 2 2 2 2 2 1 9 9 9 9 0 14 15 15 15 14 19 19 19
Sample Output 2
353820794
The answer is 353820794, which is 2350309500 modulo 998244353.