[dp优化] CF1582F2

· · 个人记录

题意

给出序列 a，求它的所有递增子序列的异或和？

n\le 1e6,0\le a\le5000

思路

值域很小，那很容易有一个 O(nv) 的暴力。f_i 记录异或和为 i 时的最小结尾，大力转移即可。再上些玄学优化便通过了考场数据。

然后考虑优化。发现这个状态定义太 fw 了，异或值不是呈区间的形态分布的。

故考虑修改状态，加上 结尾元素 这一维，定义 f_{i,j} 表示结尾元素 <i 且异或和为 j 的子序列是否存在。朴素复杂度 O(nv^2)，但貌似很能优化。

然后很容易发现，当同一个 a 多次出现时，有些 f_{a,j} 会被遍历多次，显然只需遍历一次即可。

那么有优化思路：开动态数组 b_a 记录 j，每次对 a 操作完后直接清空即可。复杂度均摊正确。

接着考虑优化转移：\forall p>a,a \to f_{p,a\bigoplus j}

不难发现这是个后缀。那么为了避免标记重复的 p，可以考虑 r_j 表示下次标记时直接从 f_{r_j,p} 开始即可。复杂度均摊正确。

那么优化后 O(nv^2)\to O(n+v^2)，可以通过。

此题很好体现了 及时删去重复状态 的优化思路。

小 trick 记录：