题解：AT_arc125_d [ARC125D] Unique Subsequence

· · 题解

[ARC125D] Unique Subsequence

看到题很明显是一个 dp，根据数据范围设出状态 dp_i 为以 i 结尾的只出现一次序列数。

我们需要考虑怎么处理子序列重复的问题，对于数组中两个值相同的 a_i 与 a_j（默认 i<j）,那么对于 i 以前的子序列就会分别与 a_i 和 a_j 拼接出现两次。

所以我们预处理 lst_i 为 a_i 上一次出现的位置。

注意边界处理，当 a_i 是第一次出现时，dp_i 需要加一。