← 返回题目列表

AtCoder · abc457_f

F. 第二个缺口

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

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