分数: 525 点
问题陈述
给你一个整数 N 和一个整数序列 D = (D_1, D_2, \ldots, D_{N-1}) 长度 N - 1.
求模数 998244353,排列 P = (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N) 满足以下条件。
- 对于每个 1 \le i \le N - 1,让 P_a 和 P_b 分别是其中具有最大和第二大值的元素 (P_i, P_{i+1}, \ldots, P_N);那么 |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 第二个最大值是 P_1,和 |2 - 1| = 1 = D_1.
-
我们有 (P_2, P_3) = (3, 1)。最大值为 P_2 第二个最大值是 P_3,和 |2 - 3| = 1 = D_2.
四种排列满足条件: (1, 2, 3), (1, 3, 2), (2, 3, 1), (3, 2, 1)。因此,输出 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