U205150 本质不同子序列个数

> 设 $V = \max_{i=1}^n\{a_i\}$。 > > **做法 $\bm 0$**：考虑暴力。\ 不妨直接 $\mathcal O(2^n\times n)$ 枚举每一个子序列并且计算它的 hash 值。设计一个比较良好的 hash 函数，去重即可。\ 精细实现可以 $\mathcal O(2^n)$，不过没啥必要。可以通过测试点 $1$。 > > **做法 $\bm 1$**：考虑 dp。\ 设 $f_{i,j}$ 表示 $a_{1\dots i}$ 以字符 $j$ 结尾的方案数。\ 转移，对于 $j \neq a_i$ 事实上不需要任何更新，对于 $j = a_i$ **钦定** 最后一个数为 $a_i$ 得到转移（$+1$ 表示只选 $a_i$ 一个数）： > $$f_{i,j} = \begin{cases} f_{i-1,j}, &j \neq a_i \\ (\sum_j f_{i-1,j}) + 1, &j = a_i\end{cases}$$ > 时间复杂度 $\mathcal O(nV)$，可以通过测试点 $1{,}2{,}4$。\ > 事实上，离散化一下然后维护和可过，但是你已经接近做法 2 了。 > > **做法 $\bm{2}$**：考虑优化做法 1。\ 事实上，我们额外维护一个 $g_i = \sum_{j=1}^{\lvert \Sigma\rvert}f_{i,j}$，答案所求即为 $g_n$。\ > 对 $g_n$ 直接进行维护，观察转移：$g_n = g_{n-1}\times 2 - f_{n-1,a_n} + 1$。\ > 因为我们只想维护 $g$，考虑用 $g$ 表示那个 $f$。 > 1. 若 $a_n$ 先前没出现，可以得到 $f_{n-1,a_n} = 0$ 即 $g_n = g_{n-1}\times 2 + 1$； > 2. 若 $a_n$ 先前出现，追溯到一个最大的 $pre$ 满足 $a_{pre} = a_n$。$\forall j \in [pre, n - 1]$，容易得到所有 $f_{j} = f_{pre}$。那么看 $f_{n-1, a_n} = f_{pre, a_n}$ 的转移： > $$f_{pre, a_n} = (\sum_j f_{pre-1, j}) + 1$$ > 太美妙了！你发现没有！$f_{pre, a_n} = g_{pre - 1} + 1$！！！\ 所以这里直接化为 $g_n = g_{n - 1}\times 2 - g_{pre \color{red}-1}$ 即可。\ > 讨论完毕，可以直接维护 $g$。\ 时间复杂度 $\mathcal O(n\log n)$。其实搞不懂为啥大家可以直接 skip 到做法 2，反正我是没这个能力，单看网上题解也看不懂。 > > **做法 $\bm{3}$**：考虑不以值结尾作为 dp 维度而以下标结尾作为 dp 维度。\ > 具体地，设 $f_i$ 表示 $a_{1\dots i}$ 的不在 $a_{1\dots (i-1)}$ 内出现的子序列个数。\ > 转移可以更加直接，按照下标的思路，枚举前一个数： > $$f_i = \sum_{j=pre}^{i-1}f_j$$ > 容易证明这是正确的。直接实现是 $\mathcal O(n\min(n, V))$ 的（通过测试点 $1\sim 4$），前缀和优化就可以做到 $\mathcal O(n\log n)$。\ > **Warning**：采用该做法求解诸如固定 $a_n$ 必须选，答案不是 $f_n$，是 $f_n + f_{pre_n} + f_{pre_{pre_n}} + \dots$。时刻根据定义出发。

给出一个长度为 $n$ 的序列 $a_1\dots a_n$，求它的本质不同子序列个数。 答案对 $998244353$ 取模。

第一行一个整数 $n$。 接下来一行 $n$ 个整数 $a_1\dots a_n$。

一行一个整数表示答案。

### 数据规模与约定 + 测试点 1（10 pts）：$n \leq 22$，$a_i \leq 5000$。 + 测试点 2（10 pts）：$n \leq 5000$，$a_i \leq 5000$。 + 测试点 3（10 pts）：$n \leq 5000$。 + 测试点 4（10 pts）：$a_i \leq 5000$。 + 测试点 5 ~ 8（15 \* 4 = 60 pts）：无特殊限制。 对于所有数据，$1 \leq n \leq 3\times 10^5$，$1 \leq a_i \leq 2\times 10^9$。