#P1370. Charlie的云笔记序列

Charlie的云笔记序列

题目背景

Charlie 是 oiinhand 的忠实粉丝。他有使用 oih 云笔记记录自己的题解的习惯。只有一点一滴的积累才能留下自己的足迹。

oih 云笔记有什么特点吗?

oih 的站长 soha 表示,目前 oih2 的云笔记功能比较简陋,但是正在开发 oih3 中的新版云笔记功能将是世界上最适合 oier 的储藏笔记的工具。

首先,新版云笔记支持 markdown 功能,并且可以实时预览,插入公式图片都不是问题。实时自动保存,不用担心突然断电啊文档消失,而且不管在哪里都可以看!

其次,可以一键生成题解模板摘要,不用各种复制粘贴了,超省事!

再者,云笔记可以给其他同学分享自己的笔记,共同进步。写完了笔记,还可以一键向洛谷投稿呢!

然而 Charlie 最喜欢的功能是 oih 的题目收藏。现在他收藏了一系列题目,但是觉得不过瘾所以正在玩弄这个功能。

题目描述

某天,Charlie 将收藏的题目抽象为一个序列。a=[a1,a2,a3,,an1,an]a=[a_1,a_2,a_3,\cdots,a_{n-1},a_n]

a[l:r]a[l:r] 表示序列 ai{a_i}ll 个数到第 rr 个数之间的子串,其中 1lrn1 \le l \le r \le n。形式化地,a[l:r]=al,al+1,al+2,,ar1,ara[l:r]={a_l,a_{l+1},a_{l+2},\cdots,a_{r-1},a_r}。比如说,a=[9,8,0,3,2,1]a=[9,8,0,3,2,1],那么 a[2:5]=[8,0,3,2]a[2:5]=[8,0,3,2]

Charlie 对序列 [ai][a_i] 定义了一个函数 F(l,r)F(l,r),表示序列 a[l:r]a[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}]$,其中 li1<i2<i3<<ik1<ikrl \le i_1<i_2<i3<\cdots<i_{k-1}<i_k \le r。比如说,a=[9,8,0,3,2,1]a=[9,8,0,3,2,1],那么 [8,3,2][8,3,2]a[2:5]=[8,0,3,2]a[2:5]=[8,0,3,2] 的一个子序列。

长度为 nn 的序列 aa 和长度为 mm 的序列 bb 被称作本质不同的,当且仅当 nmn\neq m,或存在 ii,使得 aibia_i \neq b_i。反之,则称这 22 个序列是本质相同的。比如说,[9,8][9,8][9,7][9,7] 是本质不同的,[9,8][9,8][9,8,7][9,8,7] 也是本质不同的,而 [9,8][9,8][9,8][9,8] 是本质相同的。

举个例子,设 a=[1,9,9,8,0,3,2,1]a=[1,9,9,8,0,3,2,1],那么 F(1,3)=6F(1,3)=6,因为 a[1:3]=[1,9,9]a[1:3]=[1,9,9]66 个子序列:[],[1],[9],[1,9],[9,9],[1,9,9][],[1],[9],[1,9],[9,9],[1,9,9]

现在 Charlie 想知道,1lrnF(l,r)\sum _{1\le l\le r\le n} F(l,r) 的值是多少。由于这个数可能很大,请输出它对 9982443539982443537×17×223+17\times 17\times 2^23+1,一个质数)取模后的结果。

输入格式

第一行一个整数 nn,表示序列 aa 的长度。

第二行包括 nn 个整数,表示 a1,a2,a3,an1,ana_1,a_2,a_3,\cdots a_{n-1},a_n

输出格式

一行,一个整数表示 1lrnF(l,r)\sum _{1\le l\le r\le n} F(l,r) 的值对 998244353998244353 取模后的结果。

8
1 9 9 8 0 3 2 1
814

提示

  • 对于 10%10\% 的数据,1n101\le n \le 10
  • 对于 30%30\% 的数据,1n1001 \le n \le 100
  • 对于 50%50\% 的数据,1n10001\le n \le 10000ai1050 \le a_i \le 10^5
  • 对于 100%100\% 的数据,1n1051 \le n \le 10^5ai109|a_i| \le 10^9

oiinhand 3.0 正在开发中。

这将是 oiers 都需要的工具,它不仅集合了全网所有大型 OJ 的资源(题目、题解)而且针对用户还可以将自己在其他 OJ 评测过的代码储存下来,并且有超贴心的云笔记功能,帮助大家最大效率练习。

soha 借此地征求意见,有奖哦!http://www.wenjuan.com/s/M7fqIv/