[题解] CF1849F XOR Partition

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

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

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

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