← 返回题目列表

AtCoder · arc186_d

D. 波兰狂热

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

分数: 900 点

问题陈述

是否为非空非负整数序列 (V_1, V_2, \dots, V_M) is 波兰语 或 not 递归定义如下:

  • 我们说 (V_1, V_2, \dots, V_M) 是波兰语(如果存在) V_1 波兰序列 W_1, W_2, \dots, W_{V_1} 这样序列的串联 (V_1), W_1, W_2, \dots, W_{V_1} 按此顺序等于 (V_1, V_2, \dots, V_M).

特别是,序列 (0) 是波兰语。

给定一个非负整数序列 (A_1, A_2, \dots, A_N) 长度 N,求长度为波兰序列的数量 N 按字典顺序不大于 (A_1, A_2, \dots, A_N),模数 998244353.

序列的字典顺序是什么?

我们说这个序列 S = (S_1,S_2,\ldots,S_{|S|}) is 按字典顺序排列较少 比序列 T = (T_1,T_2,\ldots,T_{|T|}) 如果下面的条件 1. 或 2. 成立。 在这里, |S|, |T| 代表的长度 分别为 S, T 。

  1. |S| \lt |T| 和 (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|}).
  2. 存在一个整数 1 \leq i \leq \min\lbrace |S|, |T| \rbrace 使得以下两者成立:
    • (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})
    • S_i (数字上)小于 T_i.

约束

  • 1\leq N \leq 3\times 10^5
  • 0\leq A_i \lt N
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \dots A_N

输出

打印满足条件的序列数,模数 998244353.


示例输入 1

6
1 1 1 2 0 0

示例输出 1

2

(1, 1, 1, 1, 1, 0) 和 (1, 1, 1, 2, 0, 0) 满足条件。

我们可以验证 (1, 1, 1, 2, 0, 0) 的波兰语如下。

  • 如问题陈述中所述, (0) 是波兰语。
  • (2, 0, 0) 是波兰语,因为它等于串联 (2) 和两个波兰序列 (0) 和 (0) 按此顺序。
  • (1, 2, 0, 0) 是波兰语,因为它等于串联 (1) 和一个波兰序列 (2, 0, 0) 按此顺序。
  • (1, 1, 2, 0, 0) 是波兰语,因为它等于串联 (1) 和一个波兰序列 (1, 2, 0, 0) 按此顺序。
  • (1, 1, 1, 2, 0, 0) 是波兰语,因为它等于串联 (1) 和一个波兰序列 (1, 1, 2, 0, 0) 按此顺序。

示例输入 2

11
3 3 4 4 5 5 6 6 7 7 8

示例输出 2

13002

示例输入 3

19
18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18

示例输出 3

477638700

示例输入 4

4
1 1 0 0

示例输出 4

0