自动搬运

查看原文

来自洛谷，原作者为

	览遍千秋 将伤与泪汇成力化作拳

搬运于2025-08-24 22:55:42，当前版本为作者最后更新于2024-02-27 14:13:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本题解为官方题解。

首先，证明一个结论：对于任意的 $a < b < c$。都有 $a \oplus c > \min(a \oplus b , b \oplus c)$。

证明：假设 $a$ 与 $c$ 二进制表示中 $a$ 与 $c$ 不一样的最高位为第 $i$ 位，由 $a < c$ 可知 $a$ 这一位为 $0$，$c$ 这一位为 $1$。由 $a < b < c$ 可知 $b$ 在高于第 $i$ 位的每一个二进制位一定与 $a$ 和 $c$ 一样。若 $b$ 的第 $i$ 为为 $0$，则 $a$ 与 $b$ 二进制表示不一样的最高位低于第 $i$ 位，即 $a \oplus b < a\oplus c$。同理，如果 $b$ 的第 $i$ 位为 $1$，那么则有 $b \oplus c < a\oplus c$。将两种情况总结即可得到 $a \oplus c > \min(a \oplus b , b \oplus c)$。

根据上面的结论即可得到，一个集合中任意两个正整数的异或的最小值一定出现在集合中大小关系上相邻的两个数之间。

于是，将集合 $S$ 中所有元素从小到大排序得到数组 $a$，此问题则等价于将数组 $a$ 划分为两个非空子序列 $b_1 , b_2$，使得 $b_1$ 中任意两个相邻元素的异或大于等于 $k_1$，且 $b_2$ 中任意两个相邻元素的异或大于等于 $k_2$ 的方案数。

考虑使用动态规划解决此问题：将数组 $a$ 中每个正整数从前向后依次添加到数组 $b_1$ 或数组 $b_2$ 中。设 $dp_{i,j}$ 表示子序列 $b_1$ 末尾元素为 $a_i$，且子序列 $b_2$ 末尾元素为 $a_j$ 时的方案数。当添加一个数组 $a$ 中的元素到数组 $b_1$ 或 $b_2$ 中时，枚举所有的 $(i,j)$ 并判断是否满足异或限制的条件进行转移。这样即可得到一个 $O(n^3)$ 的动态规划做法，但无法通过此题。

考虑优化上述动态规划做法：由于插入数组 $a$ 中第 $i$ $(i > 1)$个正整数时，两个子序列 $b_1 , b_2$ 中一定刚好有一个子序列末尾为 $a_{i-1}$。于是可以用一个 $0/1$ 变量记录 $b_1 , b_2$ 中哪个子序列末尾为第 $i-1$ 个元素，并记录另一个子序列末尾的位置，将时间复杂度优化到 $O(n^2)$。但仍然无法通过此题。

继续优化上述做法：对于数组 $b_1$ 的末尾为数组 $a$ 第 $i-1$ 个数的情况，将数组 $b_2$ 末尾所有可能的数和对应的方案数插入到一个字典树中。对于数组 $b_2$ 的末尾为数组 $a$ 第 $i-1$ 个数的情况，将数组 $b_1$ 末尾所有可能的数和对应的方案数插入到另一个字典树中。将数组 $a_i$ 个数插入到 $b_1 , b_2$ 中的一个数组时，讨论 $a_{i-1}$ 此时的位置在 $b_1 . b_2$ 哪个数组的末尾，分四种情况讨论转移。单次转移即为查询字典树中所有与 $a_i$ 异或不超过 $k_1$ 或 $k_2$ 的数的总数。单次查询可以在 $O(\log(\max(a)))$ 时间内做到。

总时间复杂度和空间复杂度均为 $O(n \cdot \log(\max(a)))$。