CF1870E Another MEX Problem 题解-526互联

首先 \(O(n^3)\) 的 dp 是 simple 的。设 \(dp_{i,j}\) 表示前 \(i\) 个划分后异或和为 \(j\) 是否可行。因为转移不具有连续性，故bitset无法优化(其实 \(O(\frac{n^3}{\omega})\) 也跑不过去)

官方做法：

定义对于一个区间 \([l,r]\) 中不存在 \(l \leq l' \leq r' \leq r\) 满足 \(mex(l,r) = mex(l',r')\) ，则称这个区间为“好的区间” 。好的区间只有 \(O(n)\) 个。
证明：不妨设 \(a_l > a_r\) ，显然有 \(a_l < mex(l,r)\) ，假设对于以 \(l\) 为左端点存在另一个好的区间 \([l,r']\) 满足 \(r' > r\) 且 \(a_l > a_{r'}\) ，则 \(a_{r'} < a_l < mex(l,r)\) ，说明 \(a_{r'}\) 一定已经在 \([l,r]\) 中出现过了，一定不会产生有效贡献，因此 \([l,r']\) 不可能是一个“好的区间”
对于 \(a_l < a_r\) 的情况同理，只需固定右端点即可
因此只需要预处理出“好的区间”，然后 \(O(n^2)\) 做刚才的 dp 即可

然后再说一个别的做法：

发现 \(dp_{i,j}\) 如果一个位置是 \(1\) ，那他的后缀都是 \(1\) ，因此显然你能选的位置越靠前越优
故设 \(f_x\) 表示可以凑出异或和为 \(x\) 的最小下标
怎么计算呢？我们可以计算 \(g_{i,x}\) 表示从 \(i\) 位置后面(包含)开始，满足 \(mex(i,g_{i,x}) = x\) 的最小的 \(g_{i,x}\) ，预处理是 \(O(n^2)\) 的
然后转移就比较明显了，枚举下一个区间的 \(mex\) 值是什么，\(f_{x \oplus y} \leftarrow g_{f_x+1,y}\) 。转移顺序可以枚举当前考虑的是前 \(i\) 个数，然后找到所有 \(f_x + 1 = i\) 的位置 \(x\) 进行转移

For(i, 1, n)
    For(j, 0, m - 1)
        if(f[ j ] + 1 == i)
            For(k, 0, m - 1)
                Min(f[ j ^ k ], g[ i ][ k ]);