保持异或较小题解

思路

把所有数按从高到低的二进制位插入 01 Trie。设结点 $u$ 的子树中有 $s_u$ 个数组位置，预处理 $p_i=2^i\bmod 998244353$。

核心状态 $F(u,v,b)$ 统计从结点 $u,v$ 的两棵子树中选择下标的方案数，允许空集， 并要求每一对分别来自两棵子树的已选元素在第 $b$ 位及以下的异或不超过 $x$ 的对应后缀。每棵子树内部的约束已经由更高位决定：若当前比较的是同一个结点， 内部仍需继续递归；若是两个不同结点，则这里只检查跨两棵子树的数对。

做法

子任务 1：$x=0$

任意两个被选数的异或必须为零，所以同一个合法子集中的值必须全部相等。 若值 $v$ 出现 $c_v$ 次，它贡献 $2^{c_v}-1$ 个非空下标子集。因此答案为

这是一条独立于 Trie DP 的线性或排序计数算法。

子任务 2：$n\le 22$

预处理每一对位置是否相容，再枚举全部 $2^n$ 个下标集合。删除集合中最低位的 位置后，可以由较小集合的合法性和新位置与其余位置的相容性在 $O(1)$ 位运算中转移。 总复杂度为 $O(n^2+2^n)$。

子任务 3：01 Trie 上的二元状态

记 $u_0,u_1$ 为 $u$ 的两个儿子，$v_0,v_1$ 同理。空结点的大小视为零。

当 $u=v$ 时：

• 若 $x$ 的第 $b$ 位为 $0$，已选元素不能同时来自两个儿子，否则它们的异或在 当前位为 $1>x_b$。故$$F(u,u,b)=F(u_0,u_0,b-1)+F(u_1,u_1,b-1)-1.$$
• 若 $x$ 的第 $b$ 位为 $1$，同侧元素之间的异或当前位为零，已经严格小于 $x$； 只有左右两侧之间的数对还需要匹配更低位。因此$$F(u,u,b)=F(u_0,u_1,b-1).$$

当 $u\ne v$ 时，状态只约束跨两棵子树的数对：

• 若 $x_b=1$，相同位的跨树数对已经严格更小，只有异位配对仍受限制，且两组互不相交：$$F(u,v,b)=F(u_0,v_1,b-1)\cdot F(u_1,v_0,b-1).$$
• 若 $x_b=0$，只要同时从两棵子树选择元素，它们就必须落在相同位。可以选择 $u_0\cup v_0$，或选择 $u_1\cup v_1$；此外还要补上只从 $u$ 中同时选择两侧、 以及只从 $v$ 中同时选择两侧的方案：$$\begin{aligned} F(u,v,b)={}&F(u_0,v_0,b-1)+F(u_1,v_1,b-1)-1\\ &+(2^{s_{u_0}}-1)(2^{s_{u_1}}-1)\\ &+(2^{s_{v_0}}-1)(2^{s_{v_1}}-1). \end{aligned}$$

边界如下：若 $u,v$ 中恰有一个为空，另一侧可任意选择，答案为 $2^{s_{u\lor v}}$； 若已经处理完全部位，则同一结点返回 $2^{s_u}$，不同结点返回 $2^{s_u+s_v}$。

最终答案是 $F(\mathrm{root},\mathrm{root},29)-1$，减去全程被计入的空集。

正确性证明

对二进制位从低到高作归纳。边界状态没有尚待比较的位：若两侧都存在，所有选择 均符合已经匹配的前缀；若一侧为空，也不存在跨侧数对，故边界公式正确。

考虑第 $b$ 位。两个数的异或与 $x$ 比较时，首次不同的高位决定大小。若 $x_b=0$，跨侧元素在该位异或为 $1$ 会立即超出限制，所以只能保留相同位的跨侧 组合；若根本没有跨侧元素，则同一棵子树内部可以任意选，这正是公式中的两个补项。 若 $x_b=1$，当前位异或为 $0$ 的数对已经严格小于 $x$，不再受低位限制，而当前位 异或为 $1$ 的两组仍须递归核对低位。各公式列出的情形互斥且覆盖全部选择方案， 递归子状态由归纳假设正确，因此当前状态也正确。

根状态要求所有已选元素之间的数对满足限制，所以它恰好统计全部合法子集以及空集。 减去空集后即为题目所求。

复杂度

• 子任务 1：时间 $O(n\log n)$（使用哈希表时期望 $O(n)$），空间 $O(n)$。
• 子任务 2：时间 $O(n^2+2^n)$，空间 $O(2^n+n)$。
• 子任务 3：每个 Trie 状态只访问常数个下一层状态，总时间 $O(30n)$， 空间 $O(30n)$。