题目翻译

E. XOR 矩阵
给定四个整数 $n, m, A, B$，统计满足以下条件的数组对 $(a, b)$ 的数量：

• $a$ 包含 $n$ 个整数，每个整数在 $[0, A]$ 范围内；
• $b$ 包含 $m$ 个整数，每个整数在 $[0, B]$ 范围内；
• 由 $a$ 和 $b$ 构造的 XOR 矩阵 $X_{i,j} = a_i \oplus b_j$ 中，不同的数值个数不超过 2。

答案对 $998244353$ 取模。

---

题解

1. 关键观察

如果数组 $a$ 或 $b$ 中至少有三个互不相同的数，那么 XOR 矩阵中也会出现至少三个不同的值。

证明：假设 $a$ 中有三个不同的数 $a_1, a_2, a_3$，任取 $b$ 中一个数 $b_1$，则 $a_1 \oplus b_1, a_2 \oplus b_1, a_3 \oplus b_1$ 互不相同。因此矩阵中至少有三个不同的值。

因此，合法情况只能出现在 $a$ 和 $b$ 各自最多包含 2 个不同数值。

所以我们将问题分成以下四部分：

1. $a$ 中所有数相同，$b$ 中所有数相同；
2. $a$ 中所有数相同，$b$ 中有 2 个不同的数；
3. $a$ 中有 2 个不同的数，$b$ 中所有数相同；
4. $a$ 和 $b$ 都恰好有 2 个不同的数。

---

2. 第一部分：$a$ 全相同，$b$ 全相同

• 选择 $a$ 中唯一的数：$A+1$ 种（$0$ 到 $A$）
• 选择 $b$ 中唯一的数：$B+1$ 种

所以第一部分答案为：

$$\text{part}_1 = (A+1)(B+1)$$

---

3. 第二部分：$a$ 全相同，$b$ 有 2 个不同的数

• 选择 $a$ 中唯一的数：$A+1$ 种
• 选择 $b$ 中的两个不同的数：从 $0$ 到 $B$ 中选两个有序数对 $(b_1, b_2)$，且 $b_1 \neq b_2$。
  先选两个不同的数值，再决定哪个是第一个哪个是第二个，但这里我们直接统计无序对更方便：
  无序对的数量为 $\binom{B+1}{2} = \frac{(B+1)B}{2}$。
• 分配 $m$ 个位置给这两个数：每个位置可以是 $b_1$ 或 $b_2$，但不能全相同，所以有 $2^m - 2$ 种分配方式。

因此第二部分答案为：

$$\text{part}_2 = (A+1) \cdot \frac{B(B+1)}{2} \cdot (2^m - 2) $$

---

4. 第三部分：$a$ 有 2 个不同的数，$b$ 全相同

对称地：

$$\text{part}_3 = (B+1) \cdot \frac{A(A+1)}{2} \cdot (2^n - 2) $$

---

5. 第四部分：$a$ 和 $b$ 都恰好有 2 个不同的数

设 $a$ 中的两个数为 $a_1 > a_2$，$b$ 中的两个数为 $b_1 > b_2$。

5.1 约束条件

XOR 矩阵由以下四个值组成：

$$\begin{aligned} & a_1 \oplus b_1, \quad a_1 \oplus b_2, \\ & a_2 \oplus b_1, \quad a_2 \oplus b_2 \end{aligned} $$

要使矩阵中不超过 2 个不同的值，必须满足：

$$a_1 \oplus b_2 = a_2 \oplus b_1$$

否则，$a_1 \oplus b_1 \neq a_1 \oplus b_2$，且 $a_1 \oplus b_1 \neq a_2 \oplus b_1$，会导致至少三个不同的值。

上述条件等价于：

$$a_1 \oplus a_2 = b_1 \oplus b_2$$

记 $x = a_1 \oplus a_2$，则 $x = b_1 \oplus b_2$，且 $x > 0$（因为 $a_1 \neq a_2$）。

并且 $a_2 = a_1 \oplus x$，$b_2 = b_1 \oplus x$。

5.2 条件转化

我们需要：

$$0 \le a_1 \oplus x < a_1 \le A$$ $$0 \le b_1 \oplus x < b_1 \le B$$

且 $x > 0$。

所以问题转化为：统计满足上述条件的三元组 $(a_1, b_1, x)$ 的数量。

5.3 数位 DP

由于 $A, B$ 可达 $2^{29}-1$，我们需要按位处理（最多 30 位）。

定义 $dp[i][fa][fb][fx]$ 表示：

• 已经处理了最高 $i$ 位（从高位到低位）
• $fa = 0$ 表示 $a_1$ 的前 $i$ 位与 $A$ 的前 $i$ 位相等，$fa = 1$ 表示已经小于 $A$
• $fb = 0$ 表示 $b_1$ 的前 $i$ 位与 $B$ 的前 $i$ 位相等，$fb = 1$ 表示已经小于 $B$
• $fx = 0$ 表示 $x$ 的前 $i$ 位全为 0，$fx = 1$ 表示已经出现过非零位（即 $x > 0$）

转移：
枚举当前位 $a\_bit, b\_bit, x\_bit \in \{0,1\}$，需要满足：

1. $a\_bit \le A$ 的当前位（如果 $fa=0$ 且 $A$ 的当前位为 0，则 $a\_bit$ 不能为 1）
2. $b\_bit \le B$ 的当前位（同理）
3. $a_1 \oplus x < a_1$ 的当前位约束：
   设 $a\_bit = p$，$x\_bit = q$，则 $p \oplus q < p$ 当且仅当 $p=0$ 且 $q=1$ 时不成立（因为 $0 \oplus 1 = 1 > 0$）。
   更严谨地，从高位到低位比较 $a_1 \oplus x$ 和 $a_1$，第一次出现不同的位必须满足 $p=1$ 且 $q=1$（此时 $p \oplus q = 0 < p=1$）。
   若当前位 $p=0, q=1$，则 $p \oplus q = 1 > p=0$，违反条件。
   若 $p=1, q=1$，则 $p \oplus q = 0 < p=1$，满足条件。
   若 $p=0, q=0$，则相等，继续比较下一位。
   若 $p=1, q=0$，则 $p \oplus q = 1 = p$，相等，继续。
   所以约束：不能出现 $(p=0, q=1)$。
4. 同理，$b_1 \oplus x < b_1$ 不能出现 $(b\_bit=0, x\_bit=1)$。

更新标志：

• $fa' = fa \text{ or } (a\_bit < A\_bit)$
• $fb' = fb \text{ or } (b\_bit < B\_bit)$
• $fx' = fx \text{ or } (x\_bit = 1)$

初始状态：$dp[0][0][0][0] = 1$（第 0 位表示最高位之前）。

最终答案：所有 $dp[K][fa][fb][1]$ 的和，其中 $K$ 是位数（如 30）。

5.4 分配位置

对于每一组 $(a_1, a_2, b_1, b_2)$：

• $a$ 中的 $n$ 个位置：每个位置可以是 $a_1$ 或 $a_2$，但不能全相同，所以 $2^n - 2$ 种。
• $b$ 中的 $m$ 个位置：每个位置可以是 $b_1$ 或 $b_2$，但不能全相同，所以 $2^m - 2$ 种。

因此第四部分答案为：

$$\text{part}_4 = \text{count\_quadruples} \cdot (2^n - 2) \cdot (2^m - 2) $$

其中 $\text{count\_quadruples}$ 是上述 DP 求得的三元组 $(a_1, b_1, x)$ 的数量（每个三元组对应唯一的 $(a_1, a_2, b_1, b_2)$，因为 $a_2 = a_1 \oplus x$，$b_2 = b_1 \oplus x$）。

---

6. 最终答案

$$\text{ans} = \text{part}_1 + \text{part}_2 + \text{part}_3 + \text{part}_4 $$

所有运算在模 $998244353$ 下进行。

---

7. 复杂度

• 数位 DP 状态数：$O(\log \max(A,B) \cdot 8)$，每层转移 $2^3=8$ 种可能，常数约 $30 \times 8 \times 8 = 1920$ 次操作。
• 总复杂度：$O(\log \max(A,B))$，可以轻松通过。

---

8. 注意事项

• 当 $n=1$ 或 $m=1$ 时，$(2^n-2)$ 可能为负，但题目保证 $n,m \ge 2$，所以安全。
• 模运算下减法要加模数。
• $2^n$ 可以用快速幂计算，或者预处理。