题目描述
给定一个长度为 n 的序列 A,现在你需要将这个序列划分为若干个区间(可以只划分为一个),要求每个区间的左端点 l 和右端点 r 都满足 Al=Ar,其中 l 可以等于 r。
令这样一种合法划分的贡献为所有非空区间内元素的乘积之和(若区间内只有一个元素,那么认为这个区间内元素的乘积为这个元素的值)。
求所有合法划分的贡献之和对 998244353 取模的值。
输入格式
共两行。
第一行一个正整数 n,表示序列长度。
第二行 n 个正整数,表示序列 A。
输出格式
共一行一个整数,表示所有合法划分的贡献之和对 998244353 取模的值。
4
1 2 2 1
16
6
1 2 2 1 2 2
104
提示
样例解释
对于样例一中的序列 ⟨1,2,2,1⟩ 共存在三种合法划分:
- 划分为 4 个区间,分别为 [1,1]、[2,2]、[3,3]、[4,4],贡献为 1+2+2+1=6。
- 划分为 3 个区间,分别为 [1,1]、[2,3]、[4,4],贡献为 1+2×2+1=6。
- 划分为 1 个区间,为 [1,4],贡献为 1×2×2×1=4。
所以总贡献的和为 6+6+4=16。
数据范围
本题采用捆绑测试。
子任务编号 |
n |
Ai |
分值 |
1 |
≤10 |
≤3 |
10 |
2 |
≤103 |
≤40 |
20 |
3 |
≤2.5×105 |
≤2 |
30 |
4 |
≤40 |
40 |
对于 100% 的数据,保证 1≤n≤2.5×105,1≤Ai≤40。