题解：CF2187D Cool Problem

ran_qwq · 2026-04-22 19:52:19 · 题解

在 duel 中想到的神奇思路，但当时脑子一团乱麻写炸了调不过样例，队友帮我调出来了。

将 c 写作 ax+by 的形式。遇到一个 0 时将 a 增加 1；遇到一个 1 时将 a 取反，b 异或 1。

再将 f 也写作 Ax+By 的形式。B 的贡献相对简单：可以发现 i 对 B 有贡献当且仅当 1\sim i 中有奇数个 1。至于 A 的贡献，手玩发现遇到第一个 1 时取反后 -a 和末尾的那个 a 抵消了，所以无论何时没有被抵消的 a 形如 1\sim k 的一段等差数列。

问题是如何找到这个 k。我们以 i 为横坐标、a 为纵坐标画折线图。考虑所有 a=0 的点将折线图划分成若干段，其中最后一段是没满的。发现除了最后一段其他段都是被抵消的，所以 A=\frac{|a_n|(|a_n|+1)}2。

对于最后一段，1\sim i 中有奇数个 1 的 i 让 |a| 减 1，有偶数个 1 的 i 让 |a| 加 1。且除了最后一段其他段不对 |a| 产生贡献。发现 2(i-|a|) 等于 1\sim i 中有奇数个 1 的 i 的数量。直接用 bitset 优化 dp 维护它即可，f_{i,j,0/1} 表示 1\sim i 中有奇数个 1 的 i 的数量为 j，当前 1\sim i 中 1 的数量是偶数还是奇数，是否可行。

这是代码，很短。