[题解] CF1849F XOR Partition

· · 题解

其他题解咋都这么复杂的。来个 O(n\log V) 简单做法。

从高到低考虑当前最高位 i 是否为 1。能为 1 当且仅当第 i 位的 0、1 个数各不超过两个：此时可以枚举方案。

否则第 i 位一定为 0。由于位 i 不同的两个数异或没有贡献，分别向两侧递归子问题，取较小值即可。

显然可以归纳证明，对于集合大小 > 2 的子问题答案不为 \infty。

代码