题解：CF2187D Cool Problem

Monomial · 2026-02-04 10:17:56 · 题解

来个人类可以想到的做法。

对 x,y 分开考虑。若只算 x 的话，s_i=\texttt{0} 会使得 c_i=c_{i-1}+x，否则是 c_i=-c_{i-1}。观察一下，可以发现 \sum c_i 为 \frac{a(a+1)}{2}x 的形式。若只算 y 的话，s_i=\texttt{0} 会使得 c_i=c_{i-1}，否则是 c_i=y-c_{i-1}。同理可以发现 \sum c_i 是 by 的形式。

先将序列变成前缀异或后的结果，接下来考虑假设我们知道 0 和 1 的数量，应该如何算出 a 和 b。首先，b 是好算的，其等于 1 的数量。接着考虑 a，则可以发现连着的 0 和 1 是可以抵消的，那 +x 的次数应当是 \max(cnt_0,cnt_1)-\min(cnt_0,cnt_1)。但我们注意到若开头是 1，那么等价于翻转，其对初始情况是无效的，所以此时若上式非零，则要减去 1。

根据上面的思考，我们只需要记录序列中 1 的个数即可，所以我们设 f_{i,j,0/1} 表示长度为 i 的前缀，有 j 个 1，最后一位的值是 0 还是 1。直接 DP 是 \mathcal{O}(n^2) 的，用 bitset 优化可以做到 \mathcal{O}(\frac{n^2}{w})。计算答案部分，根据状态可以知道只有 \mathcal{O}(n) 种，每种算出来去重即可，这部分是 \mathcal{O}(n \log n) 的。

所以总时间复杂度就是 \mathcal{O}(\frac{n^2}{w})。空间复杂度用滚动数组可以优化到 \mathcal{O}(n)。