Official Editorial
https://mitit.org/static/archive/2024Spring/editorials/MITIT_2024_Spring_Finals_Editorials.pdf
5. 避免异或为零 (Avoid XOR Zero)
题目构思： Anton Trygub
题目准备： Anton Trygub
分析撰写： Anton Trygub
让我们分析在什么情况下一个特定的数组 $A_1, A_2, \dots, A_N$ 是“不可避免的”。
如果存在某个 $i$ 使得 $A_i = 0$，我们可以忽略它。让我们假设所有的 $A_i$ 都是非负的。
令 $tr(x)$ 表示 $x$ 的二进制表示中末尾连续 1 的个数（即 $x$ 的二进制形式以 $tr(x)$ 个 1 结尾）。考虑某个位 $b \ge 0$ 和某个数 $x$。我们将分析在满足 $y + z = x$ 的 $(y, z)$ 对中，有多少个数在第 $b$ 位上是 1。
- (a) 如果 $tr(x) \ge b + 1$，那么 $y$ 和 $z$ 中恰好有一个数在第 $b$ 位上是 1：因为 $x$ 以 $b+1$ 个 1 结尾，所以这些 1 将分布在 $y$ 和 $z$ 之间。
- (b) 如果 $tr(x) \le b$，我们总是可以找到 $y, z \ge 0$ 且 $y + z = x$，使得它们都不包含第 $b$ 位。确实如此：考虑 $y_1 = (x - (2^{tr(x)} - 1)) / 2$，$z_1 = y_1 + (2^{tr(x)} - 1)$。那么 $y_1, z_1$ 仅在最后 $tr(x)$ 位不同，而在所有之前的位上相同。如果 $y_1, z_1$ 都包含第 $b$ 位，那么数对 $(y_1 + 2^b, z_1 - 2^b)$ 都将不包含第 $b$ 位。
- (c) 如果 $tr(x) \le b$ 且 $x \ge 2^{b+1}$，我们总是可以找到 $y, z \ge 0$ 且 $y + z = x$，使得它们都包含第 $b$ 位。确实如此：选择上述的 $y_1, z_1$；如果两者都不包含第 $b$ 位，且 $z_1 \ge y_1$，那么数对 $(y_1 + 2^b, z_1 - 2^b)$ 都是非负的且都包含第 $b$ 位。
令 $m = \max_{1 \le i \le n} tr(A_i)$。让我们证明，如果存在一个数 $\ge 2^{m+1}$，则该数组是“可避免的”（avoidable）。确实如此：对于每个 $A_i$，我们可以将其拆分为 $B_i + C_i = A_i$，使得 $B_i, C_i$ 都不包含第 $m$ 位；而对于某个 $A_i$，我们可以将其拆分为 $B_i + C_i = A_i$，使得 $B_i, C_i$ 都包含第 $m$ 位。那么，无论我们选择哪个 $X_i \in \{B_i, C_i\}$，它们的异或和总是包含第 $m$ 位。
因此，所有数都必须 $\le 2^{m+1} - 1$。由于对所有 $i$ 都有 $tr(A_i) \le m$，所有数都 $\le 2^{m+1} - 2$。 此时，满足 $tr(A_i) = m$ 的那个数必须等于 $2^m - 1$。
令 $x_i$ 表示 $x$ 的第 $i$ 位。令 $parity(x, (b_1, b_2, \dots, b_t))$ 表示 $x_{b_1} \oplus x_{b_2} \oplus \dots \oplus x_{b_t}$（即指定位置的位的异或和）。
引理 5.1. 对于某个 $1 \le k \le m - 1$，假设以下条件之一成立：
- (a) $tr(x) \neq k$，且 $tr(x) \le m$
- (b) $tr(x) = k$，但 $2^m \le x < 2^{m+1}$
则存在非负整数 $y+z=x$，使得 $parity(y, (k-1, k, m)) = parity(z, (k-1, k, m))$。
证明。 首先，将 $x$ 拆分为 $x = y_1 + z_1$，其中 $y_1 = (x - (2^{tr(x)} - 1)) / 2$，$z_1 = y_1 + (2^{tr(x)} - 1)$。 $y_1, z_1$ 仅在最后 $tr(x)$ 位不同。因此，如果 $tr(x) \neq k$ 且 $tr(x) \le m$，则 $y_1$ 和 $z_1$ 在第 $m$ 位上没有差异，并且在第 $k-1$ 和 $k$ 位上要么都不同，要么都相同。这证明了 (a)。 如果 $tr(x) = k$ 且 $2^m \le x < 2^{m+1}$，则 $parity(x, (k-1, k, m)) = 0$，因此我们可以将 $x$ 拆分为 $(x, 0)$，从而证明了 (b)。
假设存在 $1 \le k < m$，使得不存在满足 $A_i < 2^m$ 且 $tr(A_i) = k$ 的 $A_i$。让我们证明该数组是“可避免的”。 对于每一个 $A_i \neq 2^m - 1$，我们可以将其拆分为 $A_i = B_i + C_i$，使得 $parity(B_i, (k-1, k, m)) = parity(C_i, (k-1, k, m))$。因此，无论我们选择什么 $x_i$，对于它们的异或和 $X$，值 $parity(X, (k-1, k, m))$ 是固定的。现在，只需拆分 $2^m - 1$，使得最终的 $parity(X, (k-1, k, m))$ 为奇数：如果我们不想翻转 $X$ 的奇偶性，则拆分为 $(2^m - 1, 0)$；如果想翻转，则拆分为 $(2^m - 1 - 2^k, 2^k)$。
现在假设对于所有 $1 \le k < m$，都存在满足 $tr(A_i) = k$ 且 $A_i \le 2^m - 1$ 的 $A_i$。 则该数组是“不可避免的”。 如果 $tr(A_i) = k$，那么对于任何满足 $B_i + C_i = A_i$ 的非负整数 $B_i, C_i$，$B_i \oplus C_i$ 以 $\underbrace{0}_{1} \underbrace{1 \dots 1}_{k \text{ 个 } 1}$ 结尾。
引理 5.2. 假设 $m$ 个数 $x_1, x_2, \dots, x_m \le 2^m - 1$，满足 $x_i$ 的二进制形式以 $\underbrace{0}_{1} \underbrace{1 \dots 1}_{i \text{ 个 } 1}$ 结尾。这 $m$ 个数构成一个异或基（因此我们可以将这些数中的某些进行异或，来表示任何 $\le 2^m - 1$ 的数）。
证明。 注意 $x_m = 2^m - 1$，$x_{m-1} = 2^{m-1} - 1$，因此我们可以通过它们的组合得到第 $m-1$ 位。 如果对于某个 $k$，$2^t$ 存在于它们的组合中（对于每个 $t = k, k+1, \dots, m-1$），那么考虑 $x_{k+1} \oplus x_k$：其最小的非零位是 $k-1$，因此 $2^{k-1}$ 也可以表示为某些 $x_i$ 的异或。因此，我们可以通过归纳法证明这对所有 $k$ 都成立。
因此，无论选择什么 $B_i, C_i$：
- 如果 $A_i \ge 2^m$，选择 $X_i < 2^m$
- 否则，从 $X_i = B_i$ 开始。注意我们有一个选项可以将最终的异或和异或上 $B_i \oplus C_i$。
- 根据我们的引理，我们可以将这个异或和异或上任何 $\le 2^m - 1$ 的数，因此可以使其变为 0。
现在，我们可以表述数组为“不可避免”的最终条件：
断言 5.3. 数组 $(A_1, A_2, \dots, A_N)$ 是不可避免的，当且仅当其所有元素均为 0，或者存在某个 $m \ge 1$，使得：
- 对所有 $i$，$0 \le A_i \le 2^{m+1} - 2$
- 对于每一个 $1 \le k \le m$，存在 $A_i$ 满足 $A_i < 2^m$ 且 $tr(A_i) = k$
考虑到这一点，计算不可避免数组的数量就很容易了。固定 $m$，则所有数字都必须 $\le 2^{m+1} - 1$，并且对于每个 $1 \le k \le m$，我们必须至少选择一个满足 $A_i < 2^m$ 且 $tr(A_i) = k$ 的数字。我们可以用 $t_k$ 表示此类数字的数量，并进行标准的动态规划 $dp[len][k]$：长度为 $len$ 的数组有多少个，其中所有数字都 $< 2^m$，且对于每个 $1 \le k_1 \le k$，存在一个数 $x$ 满足 $tr(x) = k_1$。状态转移方程为： $$ dp[len][k] = \sum_{0 \le len_1 < len} dp[len_1][k-1] \cdot \binom{len}{len_1} \cdot t_k^{len - len_1} $$
对于固定的 $m$，我们可以在 $O(n^2 k)$ 的时间内计算这一点，这给出了最终的时间复杂度 $O(n^2 k^2)$。