题解：AT_arc173_e [ARC173E] Rearrange and Adjacent XOR

tybbs · 2025-11-04 21:03:29 · 题解

单 log 做法。

前面部分就省略了（可以看其他题解），结论是：

设对答案有贡献的集合为 S，S 合法当且仅当：

• 若 n\equiv2\pmod 4 且 n\neq 2，|S|\neq n。

设 b_i=a_i\oplus a_1(i>1)，那么取 b 的一个子集，其异或的贡献对应 a 的一个偶数大小的子集，反之亦然。所以问题转化为：

• 在 n\equiv2\pmod 4 且 n\neq 2 时，求出 b_i 异或和最大的一个非全集子集。
• 否则，求出 b_i 异或最大的一个子集。

第二种情况是简单的线性基板子。对于第一种情况，先求出异或和最大的子集，设异或和为 x，全集的异或和为 S，若 x>S，答案即为 x。
否则需要判断全集是否时唯一一种取到 x 的方案。如果不是，等价于存在两个异或和相等的子集，即 b_i 不是线性无关的，可以在把元素插入线性基时判断。如果全集是唯一的的方案，直接求出线性基中的次大值，否则答案就是 x。

复杂度 O(n\log V)。