题目背景
Charlie 是 oiinhand 的忠实粉丝。他有使用 oih 云笔记记录自己的题解的习惯。只有一点一滴的积累才能留下自己的足迹。
oih 云笔记有什么特点吗?
oih 的站长 soha 表示,目前 oih2 的云笔记功能比较简陋,但是正在开发 oih3 中的新版云笔记功能将是世界上最适合 oier 的储藏笔记的工具。
首先,新版云笔记支持 markdown 功能,并且可以实时预览,插入公式图片都不是问题。实时自动保存,不用担心突然断电啊文档消失,而且不管在哪里都可以看!
其次,可以一键生成题解模板摘要,不用各种复制粘贴了,超省事!
再者,云笔记可以给其他同学分享自己的笔记,共同进步。写完了笔记,还可以一键向洛谷投稿呢!
然而 Charlie 最喜欢的功能是 oih 的题目收藏。现在他收藏了一系列题目,但是觉得不过瘾所以正在玩弄这个功能。
题目描述
某天,Charlie 将收藏的题目抽象为一个序列。a=[a1,a2,a3,⋯,an−1,an]。
设 a[l:r] 表示序列 ai 第 l 个数到第 r 个数之间的子串,其中 1≤l≤r≤n。形式化地,a[l:r]=al,al+1,al+2,⋯,ar−1,ar。比如说,a=[9,8,0,3,2,1],那么 a[2:5]=[8,0,3,2]。
Charlie 对序列 [ai] 定义了一个函数 F(l,r),表示序列 a[l:r] 的本质不同的子序列个数。特别地,一个空序列也被当作一个本质不同的子序列。
序列 a[l:r] 的子序列定义为 $[a_{i_1},a_{i_2},a_{i_3},\cdots,a_{i_{k-1}},a_{i_k}]$,其中 l≤i1<i2<i3<⋯<ik−1<ik≤r。比如说,a=[9,8,0,3,2,1],那么 [8,3,2] 是 a[2:5]=[8,0,3,2] 的一个子序列。
长度为 n 的序列 a 和长度为 m 的序列 b 被称作本质不同的,当且仅当 n=m,或存在 i,使得 ai=bi。反之,则称这 2 个序列是本质相同的。比如说,[9,8] 和 [9,7] 是本质不同的,[9,8] 和 [9,8,7] 也是本质不同的,而 [9,8] 和 [9,8] 是本质相同的。
举个例子,设 a=[1,9,9,8,0,3,2,1],那么 F(1,3)=6,因为 a[1:3]=[1,9,9] 有 6 个子序列:[],[1],[9],[1,9],[9,9],[1,9,9]。
现在 Charlie 想知道,∑1≤l≤r≤nF(l,r) 的值是多少。由于这个数可能很大,请输出它对 998244353(7×17×223+1,一个质数)取模后的结果。
输入格式
第一行一个整数 n,表示序列 a 的长度。
第二行包括 n 个整数,表示 a1,a2,a3,⋯an−1,an。
输出格式
一行,一个整数表示 ∑1≤l≤r≤nF(l,r) 的值对 998244353 取模后的结果。
8
1 9 9 8 0 3 2 1
814
提示
- 对于 10% 的数据,1≤n≤10;
- 对于 30% 的数据,1≤n≤100;
- 对于 50% 的数据,1≤n≤1000,0≤ai≤105;
- 对于 100% 的数据,1≤n≤105,∣ai∣≤109。
oiinhand 3.0 正在开发中。
这将是 oiers 都需要的工具,它不仅集合了全网所有大型 OJ 的资源(题目、题解)而且针对用户还可以将自己在其他 OJ 评测过的代码储存下来,并且有超贴心的云笔记功能,帮助大家最大效率练习。
soha 借此地征求意见,有奖哦!http://www.wenjuan.com/s/M7fqIv/