T3. 禁止套娃

题意

求一个序列的所有本质不同子序列的本质不同子序列个数之和 $\bmod 1000000007$。$n\le 5000$。

算法一

计算一个序列的本质不同子序列个数的方法如下：

由于会计重，考虑对于每一种子序列，钦定只对它最靠左（贪心）的匹配计数。容易证明存在唯一的这样的子序列到下标的映射。

令 $dp_i$ 表示末尾选 $i$ 的本质不同子序列数，则 $dp_0=1,dp_i=\sum_{j=pre_i}^{i-1}dp_j$，$pre_i$ 表示上一个与 $a_i$ 相等的位置，如果不存在则为 $0$。

或者，令 $dp_i$ 表示末尾选 $\le i$ 的本质不同子序列数，则 $dp_0=1,dp_i=2dp_{i-1}-dp_{pre_i-1}$。

外层暴枚可做到 $\mathrm{O}(n2^n)$，期望得分 $30$。

算法二

直接讲正解。

设选择的外层子序列下标为集合 $I$，内层为集合 $J\subseteq I$。为了方便表述，设占位下标 $0\in I,J$。同样只计贪心匹配的情况，限制如下：

1. $I$ 中相邻两个数 $i,i'$，$a_{i+1\sim i'-1}$ 中不存在 $=a_{i'}$ 的值。
2. $J$ 中相邻两个数 $j,j'$，$a_{I\cap(j,j')}$ 中不存在 $=a_{j'}$ 的值。

考虑对 $J$ dp。$f_i$ 表示目前考虑到 $i$ 且内外层末尾均选 $i$ 的答案。如果要从 $f_j$ 转移过来，那么就要决定 $a_{j+1\sim i-1}$ 这部分如何选外层，设选择了集合 $K$，限制如下；

1. $K$ 中相邻两个数 $k,k'$，$a_{k+1\sim k'-1}$ 中不存在 $=a_{k'}$ 的值。
2. $K$ 中最大值 $k_r$，$a_{k_r+1\sim i-1}$ 中不存在 $=a_i$ 的值。
3. $K$ 中任意 $k$，$a_k\ne a_i$。

一个简洁的处理方法是，对于每一个 $i$，dp 出 $>$ 每个 $j$ 的只需满足 1、3 条件的本质不同子序列个数 $g_{i,j}$，真正转移时 $f_i\xleftarrow{+}(g_{i,j}-g_{pre_i,j})\cdot f_j$ 即可。最后汇总答案可以弄一个必选的占位下标 $n+1$。

$g$ 是 2D/0D，$f$ 是 1D/1D，时间复杂度 $\mathrm{O}(n^2)$，期望得分 $100$。