ARC173E 题解

EuphoricStar · 2024-03-25 18:10:04 · 题解

不妨考虑最后的结果可以成为哪些 a_i 的组合。为了方便分析，我们令 a_i = 2^{i - 1}。

进行一次操作后，所有 \text{popcount}(a_i) 都为偶数。所以一个 x \in [0, 2^n - 1] 能被生成出来的必要条件是 \text{popcount}(x) 为偶数。

然后通过打表可以发现：

• 对于 n = 2 或 n \bmod 4 \ne 2，任意一个 x \in [1, 2^n - 1] 且 \text{popcount}(x) 为偶数的 x 都能被生成出来。
• 对于 n \ne 2 且 n \bmod 4 = 2，任意一个 x \in [1, 2^n - 2] 且 \text{popcount}(x) 为偶数的 x 都能被生成出来。

考虑归纳证明。因为 a 中元素可以重排，所以不妨只考虑 2^{2k} - 1（k \ge 1）能否被生成出来：

于是现在问题变成了：选一个 a 中的包含偶数个元素的子集，最大化异或和，同时还可能有不能选全集的限制。

对于没有限制的情况，发现 a 中的任意一个包含偶数个元素的子集的异或和都可以表示成 a_1 \oplus a_2, a_1 \oplus a_3, \ldots, a_1 \oplus a_n 的一个子集的异或和。所以直接把这些数塞进一个线性基，然后查询即可。

对于有限制的情况，我们不妨钦定一个数不被选，删掉这个数，就转化成了没有限制的情况。

时间复杂度 O(n^2 \log V)。

code