#P11520. [2022省队模拟]序列划分

    ID: 10668 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 8 上传者: 标签>CF2500动态规划数据结构线段树计数DP前缀和

[2022省队模拟]序列划分

题目描述

给定一个长为 nn 的非负整数序列 A={a1,a2,…,an}A=\{a_1,a_2,\dots,a_n\}。

定义 AA 的一个划分 $D=\{d_1,d_2,\cdots,d_k,d_{k+1}\}(1=d_1<d_2<\cdots<d_k<d_{k+1}=n+1)(\forall 1\le i\le n,d_i\in \mathbb{Z})$ 将 AA 分为 S1={Ad1,Ad1+1,⋯ ,Ad2−1}S_1=\{A_{d_1},A_{d_1+1},\cdots,A_{d_2-1}\},S2={Ad2,Ad2+1,⋯ ,Ad3−1}S_2=\{A_{d_2},A_{d_2+1},\cdots,A_{d_3-1}\},⋯\cdots,Sk={Adk,Adk+1,⋯ ,Adk+1−1}S_k=\{A_{d_k},A_{d_k+1},\cdots,A_{d_{k+1}-1}\} 这 kk 个集合。

定义一个集合 SS 的 mex⁡\operatorname{mex} 函数:$\operatorname{mex}(S)=\min_{x\in \mathbb{N},x\notin S} x$。

定义一个划分 DD 的权值 f(D)=∏i=1kmex⁡(Si)f(D)=\prod_{i=1}^k\operatorname{mex}(S_i)。

记 U=∑Df(D)U=\sum_D f(D)。

求 U mod 998244353U \bmod 998244353。

输入格式

从文件 divide.in 中读入数据。

第一行输入一个正整数 nn 表示序列 AA 的长度。

接下来一行,输入 nn 个非负整数,第 ii 个非负整数表示 aia_i。

输出格式

输出到文件 divide.out 中。

输出一个非负整数表示答案。

样例

样例输入 1

4
0 1 0 2

样例输出 1

8

样例解释 1

一共有 88 个划分 DD:{1,5}\{1,5\},{1,4,5}\{1,4,5\},{1,3,5}\{1,3,5\},{1,3,4,5}\{1,3,4,5\},{1,2,5}\{1,2,5\},{1,2,4,5}\{1,2,4,5\},{1,2,3,5}\{1,2,3,5\},{1,2,3,4,5}\{1,2,3,4,5\}。

它们的权值分别为:33,2×0=02\times 0=0,2×1=22\times 1=2,2×1×0=02\times 1\times 0=0,1×3=31\times 3=3,1×2×0=01\times 2\times 0=0,1×0×1=01\times 0\times 1=0,1×0×1×0=01\times 0\times 1\times 0=0。

于是 U=3+0+2+0+3+0+0+0=8U=3+0+2+0+3+0+0+0=8。

故 U mod 998244353=8U\bmod 998244353=8,故输出 88。

样例 2

见附加文件中的 divide2.in 与 divide2.ans。

样例 3

见附加文件中的 divide3.in 与 divide3.ans。

该样例满足 ai≤10a_i\le 10。

样例 4

见附加文件中的 divide4.in 与 divide4.ans。

数据范围与提示

对于 10%10\% 的数据,n≤20n\le 20。
对于 30%30\% 的数据,n≤3000n\le 3000。
对于 60%60\% 的数据,n≤105n\le 10^5。
另有 20%20\% 的数据,ai≤10a_i\le 10。
对于 100%100\% 的数据,1≤n≤1061\le n\le 10^6,0≤ai≤1090\le a_i\le 10^9。