/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 525 点
問題文
整数 N と長さ N - 1 の整数列 D = (D_1, D_2, \ldots, D_{N-1}) が与えられます。
(1, 2, \ldots, N) の順列 P = (P_1, P_2, \ldots, P_N) であって、次の条件を満たすものの個数を 998244353 で割った余りを求めてください。
- すべての 1 \le i \le N - 1 について、 (P_i, P_{i+1}, \ldots, P_N) の中で最大の値を持つ要素を P_a 、 2 番目に大きい値を持つ要素を P_b とすると |a - b| = D_i である。
制約
- 2 \le N \le 2 \times 10^5
- 1 \le D_i \le N - i
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N
D_1 D_2 \ldots D_{N-1}
出力
条件を満たす順列の個数を 998244353 で割った余りを出力せよ。
入力例 1
3 1 1
出力例 1
4
例えば (2, 3, 1) が条件を満たしていることは、以下のように確認できます。
-
(P_1, P_2, P_3) = (2, 3, 1) である。最大の値は P_2 、 2 番目に大きい値は P_1 であり |2 - 1| = 1 = D_1 である。
-
(P_2, P_3) = (3, 1) である。最大の値は P_2 、 2 番目に大きい値は P_3 であり |2 - 3| = 1 = D_2 である。
条件を満たす順列は (1, 2, 3), (1, 3, 2), (2, 3, 1), (3, 2, 1) の 4 つです。よって 4 を出力してください。
入力例 2
5 1 2 2 1
出力例 2
0
入力例 3
15 4 4 4 4 4 4 3 2 2 2 2 2 1 1
出力例 3
70270200
Score : 525 points
Problem Statement
You are given an integer N and an integer sequence D = (D_1, D_2, \ldots, D_{N-1}) of length N - 1.
Find the number, modulo 998244353, of permutations P = (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N) that satisfy the following condition.
- For each 1 \le i \le N - 1, let P_a and P_b be the elements with the largest and the second largest values, respectively, among (P_i, P_{i+1}, \ldots, P_N); then |a - b| = D_i.
Constraints
- 2 \le N \le 2 \times 10^5
- 1 \le D_i \le N - i
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N
D_1 D_2 \ldots D_{N-1}
Output
Output the number, modulo 998244353, of permutations satisfying the condition.
Sample Input 1
3 1 1
Sample Output 1
4
For example, we can verify that (2, 3, 1) satisfies the condition as follows.
-
We have (P_1, P_2, P_3) = (2, 3, 1). The largest value is P_2 and the second largest value is P_1, and |2 - 1| = 1 = D_1.
-
We have (P_2, P_3) = (3, 1). The largest value is P_2 and the second largest value is P_3, and |2 - 3| = 1 = D_2.
Four permutations satisfy the condition: (1, 2, 3), (1, 3, 2), (2, 3, 1), (3, 2, 1). Thus, output 4.
Sample Input 2
5 1 2 2 1
Sample Output 2
0
Sample Input 3
15 4 4 4 4 4 4 3 2 2 2 2 2 1 1
Sample Output 3
70270200