题面

现有一个长度为 $n$ 的灯泡序列，其中 $k$ 个位置上的灯泡是熄灭的，其余的是点亮的。我们可以进行 $m$ 种操作，而第 $i$ 种操作是选定任意长度为 $b_i$ 的连续灯泡区间，对这个区间内所有灯泡的状态都进行一次翻转（亮变灭，灭变亮）。试求最少需要几次操作就可以让所有灯泡都被点亮。

数据范围：$1 \le n, b_i \le 4 \times 10^4, \ 1 \le m \le 64, \ 1 \le k \le 8$

题目链接：Luogu P3943: 星空

分析

差分思想

首先一个非常优雅的想法就是利用差分将区间操作变换为单点操作。不过这里我们面对的是一个 $01$ 序列，我们可以把普通的前缀和改成异或前缀和。严格地说，记 $a$ 代表原 $01$ 序列，$d$ 是原序列的异或差分数组。那么它们之间存在如下关系：

$$a_i = b_0 \oplus b_1 \oplus \dots \oplus b_i$$

这样翻转 $a$ 中的 $[l, r]$ 区间就等价于在 $b$ 中翻转 $l$ 和 $r + 1$ 两个位置，于是 $a$ 中的区间操作就转换为了 $d$ 中的单点操作（注意 $d$ 的长度是 $n + 1$ ）。

由此原问题被转换为这样一个新问题：给定一个 $01$ 序列 $d$ ，一次只能选择两个位置上的值（这两个位置间隔的距离是题面给出的 $m$ 种）并对其进行翻转，试问最少翻转多少次可以将序列翻转成目标序列？

---

我们不妨记灯亮为 $0$ ，灯暗为 $1$ 。这样的方便之处在于所有灯全亮时 $a$ 为全 $0$ ，而其对应的 $d$ 前 $n$ 个位置也为全 $0$ 。至于 $d$ 中的第 $n + 1$ 个位置，不论其为 $0$ 还是 $1$ 都不会对 $a$ 产生任何影响，因此第 $n + 1$ 位可以是任意值。

需要注意的是，题目给出了 $a$ 中 $1$ 的个数 $k \le 8$ ，这一限制对应到差分数组 $d$ 中会是怎样呢？如果我们要让 $d$ 为 $111111\dots$ ，那么 $a$ 的形式即如 $101010\dots$ 。不难发现若 $a$ 中最多有 $k$ 个 $1$ ，则 $d$ 中最多有 $2k$ 个 $1$ 。

完全背包

我们继续考虑转换后的问题。为了最小化反转次数我们显然不会选择两个 $0$ 进行翻转，因为这样只会使得 $1$ 的个数增多。那么我们可以选择：

• 选中两个 $1$ ，那么翻转后两个位置上的值都会变为 $0$ ；
• 选择一个 $0$ 和一个 $1$ ，那么这次操作后 $1$ 的个数并不会变化，其效果等效于将选中的两个位置上的值交换位置。进一步说，如果记两个位置间的距离为 $\Delta{x}$ ，则我们可以认为是 $1$ 向左或是向右移动了 $\Delta{x}$ 。

那么问题进一步转换为：给定一个 $01$ 序列，对于序列中每个 $1$ ，每一步可以向前或向后走 $k$ 种距离，如果走到的位置上也是 $1$ 则两者相消为 $0$ ，问最少需要多少步可以使得所有位置都变为 $0$ ？

---

考虑某一对 $1$ 之间的距离为 $\Delta{x}$ ，若要将这对 $1$ 相消，就需要左右两端的 $1$ 分别向左和向右移动到同一位置上。我们不妨把 $\Delta{x}$ 看作背包容量，每种可能的步数看作背包里的物品（每种步数 $v$ 要拆成 $+v$ 和 $-v$ 两个物品，因为既可以往左走又可以往右走），那么我们 $\mathcal{O}(nm)$ 跑一个完全背包就可以得到消去每一对 $1$ 所需要的最小步数。

一般图的最大匹配

在得到了消去每一对 $1$ 所需要的最小步数后 $w$ ，我们可以考虑在这两个点间建立一条价值为 $w$ 的无向边。这样一来，问题就转变为了一般图的最大匹配问题…… 大佬们可以使用带花树算法用 $\mathcal{O}(k^3)$ 级别复杂度解决之…… 当然这道题数据范围很小，所以我们也可以使用状压 DP 来解决。

最后还有一个细节，前面说了 $d$ 中第 $n + 1$ 位可以是任意值，因此如果考虑这一位会带来一些不便。我们可以这样处理：如果位置 $i$ 经过若干步可以到达第 $n + 1$ 位，我们就从 $i$ 向自己连一条边。其意义为 $i$ 可以与自己进行匹配。这样子就可以完全去掉第 $n + 1$ 位从而简化模型。

为了减小状态数量，我们不妨只考虑所有 $1$ 点。这样一来，初始状态用二进制表示就是 $11\dots1$ ，而目标状态即为 $00\dots0$ 。另外一个常见的优化是，我们不必用 $\mathcal{O}(k^2)$ 的复杂度去枚举每一个点对（那样会造成大量重复运算）。我们可以每次选取最左的 $1$ 点作为点对的一个点，然后 $\mathcal{O}(k)$ 枚举另一个点直接进行转移即可。这样子其实是可以遍历到所有状态的（反正目标状态中这个 $1$ 迟早要消去，这样转移的意义就是按顺序依次消去 $1$ ）。因此状压 DP 的复杂度为 $\mathcal{O}(k \cdot 2^k)$ 。

如果最后一部分采用状压 DP 实现，那么总的复杂度为 $\mathcal{O}(nm + k \cdot 2^k)$ 。如果能用带花树大概可以有 $\mathcal{O}(nm + k^3)$ 的复杂度，可惜我不会。最后附上 我的代码 以供参考。

%%%

• fstqwq 杨爷太强了 %%%