分数: 700 点
问题陈述
给定的是一系列 N 整数 A_1,A_2,\cdots,A_N.
查找非空子序列的数量 s of A 满足以下条件,取模 998244353.
- 只有一种方法可以提取 s 来自 A。 形式上,唯一存在一个索引序列 1 \leq idx(1)<idx(2)<\cdots<idx(k) \leq N 这样 A_{idx(i)}=s_i (1 \leq i \leq k),其中 s=(s_1,s_2,\cdots,s_k).
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq N
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \cdots A_N
输出
打印答案。
示例输入 1
3 1 2 1
示例输出 1
5
以下五个子序列满足条件。
- (1,1)
- (1,2)
- (1,2,1)
- (2)
- (2,1)
子序列 (1) 不满足条件,因为有两种方法可以提取它。
示例输入 2
4 4 2 1 3
示例输出 2
15
示例输入 3
12 1 2 3 6 9 2 3 3 9 6 1 6
示例输出 3
1178