2025真题 | 异或和 luogu-P14359

CSP-J 2025真题- 异或和，动态规划考点，适合GESP六级考生练习，难度⭐⭐⭐☆☆，洛谷难度等级普及/提高−。

P14359 [CSP-J 2025] 异或和

题目要求

题目描述

小 R 有一个长度为 $n$ 的非负整数序列 $a_1, a_2, \dots, a_n$ 。定义一个区间 $[l, r]$ ( $1 \leq l \leq r \leq n$ ) 的权值为 $a_l, a_{l+1}, \dots, a_r$ 的二进制按位异或和，即 $a_l \oplus a_{l+1} \oplus \dots \oplus a_r$ ，其中 $\oplus$ 表示二进制按位异或。
小 X 给了小 R 一个非负整数 $k$ 。小 X 希望小 R 选择序列中尽可能多的不相交的区间，使得每个区间的权值均为 $k$ 。两个区间 $[l_1, r_1], [l_2, r_2]$ 相交当且仅当两个区间同时包含至少一个相同的下标，即存在 $1 \leq i \leq n$ 使得 $l_1 \leq i \leq r_1$ 且 $l_2 \leq i \leq r_2$ 。
例如，对于序列 $[2, 1, 0, 3]$ ，若 $k = 2$ ，则小 R 可以选择区间 $[1, 1]$ 和区间 $[2, 4]$ ，权值分别为 $2$ 和 $1 \oplus 0 \oplus 3 = 2$ ；若 $k = 3$ ，则小 R 可以选择区间 $[1, 2]$ 和区间 $[4, 4]$ ，权值分别为 $1 \oplus 2 = 3$ 和 $3$ 。
你需要帮助小 R 求出他能选出的区间数量的最大值。

输入格式

输入的第一行包含两个非负整数 $n, k$ ，分别表示小 R 的序列长度和小 X 给小 R 的非负整数。
输入的第二行包含 $n$ 个非负整数 $a_1, a_2, \dots, a_n$ ，表示小 R 的序列。

输出格式

输出一行一个非负整数，表示小 R 能选出的区间数量的最大值。

输入输出样例 #1

输入 #1

4 2
2 1 0 3

输出 #1

输入输出样例 #2

输入 #2

4 3
2 1 0 3

输出 #2

输入输出样例 #3

输入 #3

4 0
2 1 0 3

输出 #3

说明/提示

【样例 1 解释】

小 R 可以选择区间 $[1, 1]$ 和区间 $[2, 4]$ ，异或和分别为 $2$ 和 $1 \oplus 0 \oplus 3 = 2$ 。可以证明，小 R 能选出的区间数量的最大值为 $2$ 。

【样例 2 解释】

小 R 可以选择区间 $[1, 2]$ 和区间 $[4, 4]$ ，异或和分别为 $1 \oplus 2 = 3$ 和 $3$ 。可以证明，小 R 能选出的区间数量的最大值为 $2$ 。

【样例 3 解释】

小 R 可以选择区间 $[3, 3]$ ，异或和为 $0$ 。可以证明，小 R 能选出的区间数量的最大值为 $1$ 。注意：小 R 不能同时选择区间 $[3, 3]$ 和区间 $[1, 4]$ ，因为这两个区间同时包含下标 $3$ 。

【样例 4】

见选手目录下的 $xor/xor4.in$ 与 $xor/xor4.ans$ 。

该样例满足测试点 $4, 5$ 的约束条件。

【样例 5】

见选手目录下的 $xor/xor5.in$ 与 $xor/xor5.ans$ 。

该样例满足测试点 $9, 10$ 的约束条件。

【样例 6】

见选手目录下的 $xor/xor6.in$ 与 $xor/xor6.ans$ 。

该样例满足测试点 $14, 15$ 的约束条件。

【数据范围】

对于所有测试数据，保证：

$1 \leq n \leq 5 \times 10^5$ , $0 \leq k < 2^{20}$ ;
对于所有 $1 \leq i \leq n$ ，均有 $0 \leq a_i < 2^{20}$ 。

测试点编号	$n \leq$	$k$	特殊性质
$1$	$2$	$=0$	A
$2$	$10$	$\leq 1$	B
$3$	$10^2$	$=0$	A
$4, 5$	$10^2$	$\leq 1$	B
$6 \sim 8$	$10^2$	$\leq 255$	C
$9, 10$	$10^3$	$\leq 255$	C
$11, 12$	$10^3$	$< 2^{20}$	无
$13$	$2 \times 10^5$	$\leq 1$	B
$14, 15$	$2 \times 10^5$	$\leq 255$	C
$16$	$2 \times 10^5$	$< 2^{20}$	无
$17$	$5 \times 10^5$	$\leq 255$	C
$18 \sim 20$	$5 \times 10^5$	$< 2^{20}$	无

特殊性质 A: 对于所有 $1 \leq i \leq n$ ，均有 $a_i = 1$ 。

特殊性质 B: 对于所有 $1 \leq i \leq n$ ，均有 $0 \leq a_i \leq 1$ 。

特殊性质 C: 对于所有 $1 \leq i \leq n$ ，均有 $0 \leq a_i \leq 255$ 。

题目分析

本题考查 异或性质、前缀和思想 以及 动态规划 (DP)。

1. 核心数学性质：前缀异或和

题目关心的区间 $[l, r]$ 的异或和。对于区间求和问题，最常用的技巧是 前缀和。同样地，对于区间异或，我们可以使用 前缀异或和。

定义 $pre[i]$ 为序列前 $i$ 个元素的异或和：

pre[i] = a_1 \oplus a_2 \oplus \dots \oplus a_i

特别地， $pre[0] = 0$ 。

根据异或的性质，特别是 归零律（ $x \oplus x = 0$ ）和 结合律，我们可以推导出区间异或和的公式：

XOR(l, r) = pre[r] \oplus pre[l-1]

推导过程如下：

展开前缀异或和定义：
- $pre[r]$ 表示从第 $1$ 个到第 $r$ 个元素的异或和： $pre[r] = a_1 \oplus a_2 \oplus \dots \oplus a_{l-1} \oplus \mathbf{a_l \oplus \dots \oplus a_r}$
- $pre[l-1]$ 表示从第 $1$ 个到第 $l-1$ 个元素的异或和： $pre[l-1] = a_1 \oplus a_2 \oplus \dots \oplus a_{l-1}$
进行异或运算：我们将 $pre[r]$ 和 $pre[l-1]$ 进行异或：
$pre[r] \oplus pre[l-1] = (\underbrace{a_1 \oplus \dots \oplus a_{l-1}}_{\text{公共前缀}} \oplus \underbrace{a_l \oplus \dots \oplus a_r}_{\text{目标区间}}) \oplus (\underbrace{a_1 \oplus \dots \oplus a_{l-1}}_{\text{公共前缀}})$
利用结合律和交换律：将相同的项放在一起（即 $a_1$ 对 $a_1$ ，…， $a_{l-1}$ 对 $a_{l-1}$ ）。由于异或运算满足交换律和结合律，我们可以随意调整运算顺序：
$= (a_1 \oplus a_1) \oplus (a_2 \oplus a_2) \oplus \dots \oplus (a_{l-1} \oplus a_{l-1}) \oplus (a_l \oplus \dots \oplus a_r)$
利用归零律消去：因为任何数异或自己都等于 0（ $x \oplus x = 0$ ），前面的公共部分全部抵消变为 0：
$= 0 \oplus 0 \oplus \dots \oplus 0 \oplus (a_l \oplus \dots \oplus a_r)$
$= a_l \oplus \dots \oplus a_r$

这正是区间 $[l, r]$ 的异或和。这个性质非常重要，它让我们能够在 $O(1)$ 的时间内通过两个前缀值的异或，快速求出任意子区间的异或和，类似于前缀和求子区间和（ $Sum(l, r) = pre[r] - pre[l-1]$ ）。

题目要求找到最多的不相交区间，使得每个区间的异或和都为 $k$ 。也就是说，如果我们要选一个以 $r$ 结尾的区间 $[l, r]$ ，必须满足：

pre[r] \oplus pre[l-1] = k

根据异或的交换律，这等价于：

pre[l-1] = pre[r] \oplus k

这意味着，当我们遍历到位置 $r$ 时，我们只需要在它前面找到一个位置 $l-1$ （即 $j$ ），满足 $pre[j] = pre[r] \oplus k$ ，那么区间 $[j+1, r]$ 就是一个符合条件的区间。

2. 动态规划 (DP) 设计

这是一个典型的线性 DP 问题。设 $dp[i]$ 表示在前 $i$ 个数中，最多能选出多少个符合条件的不相交区间。

对于当前位置 $i$ ，我们有两种选择：

不选以 $i$ 结尾的区间：此时我们只需继承前面的最优结果，即 $dp[i] = dp[i-1]$ 。
选一个以 $i$ 结尾的区间 $[j+1, i]$ ：这就要求区间异或和为 $k$ ，即 $pre[j] = pre[i] \oplus k$ （其中 $0 \le j < i$ ）。为了让总区间数最大，我们应该选择一个满足条件的 $j$ ，使得 $dp[j]$ 尽可能大。此时状态转移方程为：
$dp[i] = \max(dp[i], dp[j] + 1)$

综合起来，状态转移方程为：

dp[i] = \max(dp[i-1], \max_{j < i, pre[j] = pre[i] \oplus k} \{ dp[j] + 1 \})

为了更直观地理解上述 DP 转移过程，我们以 样例 1 为例进行手动模拟：

场景设定：

序列：a = [2, 1, 0, 3] (下标 $1 \sim 4$ )
目标异或值： $k = 2$
前缀异或数组 pre：
- $pre[0] = 0$
- $pre[1] = 2$
- $pre[2] = 2 \oplus 1 = 3$
- $pre[3] = 3 \oplus 0 = 3$
- $pre[4] = 3 \oplus 3 = 0$

DP 模拟过程：

$i=1$ (数值 2)：
- 继承： $dp[1]$ 至少为 $dp[0]=0$ 。
- 尝试选区间：需找 $j < 1$ 使得 $pre[j] = pre[1] \oplus k = 2 \oplus 2 = 0$ 。
- 发现 $pre[0]=0$ ，符合条件！构成区间 $[1, 1]$ 。
- 决策： $dp[1] = \max(dp[0], dp[0]+1) = 1$ 。
$i=2$ (数值 1)：
- 继承： $dp[2]$ 至少为 $dp[1]=1$ 。
- 尝试选区间：需找 $j < 2$ 使得 $pre[j] = pre[2] \oplus k = 3 \oplus 2 = 1$ 。
- 此前 $pre$ 值为 $\{0, 2\}$ ，无 $1$ 。无法构成新区间。
- 决策： $dp[2] = 1$ 。
$i=3$ (数值 0)：
- 继承： $dp[3]$ 至少为 $dp[2]=1$ 。
- 尝试选区间：需找 $j < 3$ 使得 $pre[j] = pre[3] \oplus k = 3 \oplus 2 = 1$ 。
- 此前 $pre$ 值为 $\{0, 2, 3\}$ ，无 $1$ 。
- 决策： $dp[3] = 1$ 。
$i=4$ (数值 3)：
- 继承： $dp[4]$ 至少为 $dp[3]=1$ 。
- 尝试选区间：需找 $j < 4$ 使得 $pre[j] = pre[4] \oplus k = 0 \oplus 2 = 2$ 。
- 发现 $pre[1]=2$ ，符合条件！这意味着区间 $[2, 4]$ (即 $a_2 \dots a_4$ ) 的异或和为 $k$ 。
- 决策： $dp[4] = \max(dp[3], dp[1] + 1) = \max(1, 1+1) = 2$ 。

最终答案： $2$ 。

通过这个过程可以看到，DP 的核心在于：在每一个位置 i，我们既要“守成”（继承 dp[i-1]），也要“进取”（查找是否存在 pre[j] 满足条件，从而接上一个新的区间）。

🤔 核心疑问解答：如何保证区间不重叠？
很多同学可能会问：“为什么直接用 $dp[j] + 1$ 就可以？怎么保证 $dp[j]$ 里统计的那些区间，和当前新选的区间 $[j+1, i]$ 不冲突？”
答案就在下标上：
$dp[j]$ 的含义是：在下标 $1 \sim j$ 的范围内，最多能选多少个不相交区间。也就是说，这里面所有被选中的区间，结束位置都 $\le j$ 。
我们新选的区间是 $[j+1, i]$ ，它的起始位置是 $j+1$ 。
因为 $j < j+1$ ，所以新区间 $[j+1, i]$ 和 $1 \sim j$ 范围内的任何区间在物理位置上都是完全错开的，绝对不可能有重叠。这就是线性 DP 的妙处，通过下标的自然分割保证了“无后效性”和“无重叠”。

3. 优化 DP (贪心 + 桶/哈希表)

直接套用上面的 DP 方程，对于每个 $i$ 都要回头遍历找 $j$ ，时间复杂度是 $O(N^2)$ ，这对于 $N=5 \times 10^5$ 的数据规模是会超时的。我们需要优化查找过程。

观察转移方程： $\max_{j < i, pre[j] = pre[i] \oplus k} \{ dp[j] \}$ 。我们需要快速找到满足 $pre[j] = \text{target}$ 的所有 $j$ 中， $dp[j]$ 最大的那个值。

我们可以维护一个数组（桶）max_val[v]，用来记录：在前缀异或和为 v 的所有位置中，最大的 DP 值是多少。即 max_val[v] = max(dp[j])，其中 pre[j] == v。

这样，当我们处理到位置 $i$ 时：

计算当前前缀异或和 curr = pre[i]。
计算我们需要寻找的目标前缀异或值 target = curr ^ k。
查找 max_val[target]。如果 max_val[target] 存在（即之前出现过满足条件的前缀和），说明我们可以形成一个新区间，此时候选答案为 max_val[target] + 1。
同时，不要忘了 $dp[i]$ 至少可以继承 $dp[i-1]$ （即代码中的 dp 变量在循环开始时就保留了上一轮的值）。
更新桶：计算出 $dp[i]$ 后，用它来更新 max_val[curr]，供后面使用。

4. 算法流程总结

初始化数组 max_val 为 -1（表示该异或值从未出现过），特别地 max_val[0] = 0（表示还未开始时，前缀异或为 0，区间数为 0）。
维护一个变量 dp，表示当前位置的最大区间数。
遍历序列，维护当前的前缀异或和 curr_xor。
对于每个位置：
- 计算需要寻找的目标前缀值 target = curr_xor ^ k。
- 如果 max_val[target] 有效，尝试更新 dp = max(dp, max_val[target] + 1)。
- 更新当前前缀异或值的记录：max_val[curr_xor] = max(max_val[curr_xor], dp)。
最后输出 dp 即为答案。

这种做法的时间复杂度是 $O(N)$ ，空间复杂度是 $O(2^M)$ （取决于数值范围，题目中 $a_i < 2^{20}$ ）。

示例代码

#include <algorithm>
#include <iostream>
#include <vector>

const int MAX_VAL = 1 << 20;  // 2^20 = 1048576, 题目限制 a_i < 2^20, k < 2^20
int max_dp[MAX_VAL];

int main() {

    // 优化 I/O 速度，避免大量输入输出导致超时
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    int k;
    std::cin >> n >> k;

    // 初始化 max_dp 数组
    // max_dp[v] 存储的是：当某个位置的前缀异或和为 v
    // 时，该位置及之前能得到的最大区间数
    for (int i = 0; i < MAX_VAL; ++i) {
        max_dp[i] = -1;
    }
    // 初始状态：还没有读取任何数时，前缀异或和为 0，区间数为 0
    max_dp[0] = 0;

    int current_xor = 0;  // 当前的前缀异或和 (pre[i])
    int dp = 0;           // 当前位置的最大区间数 (dp[i])

    for (int i = 1; i <= n; ++i) {
        int a;
        std::cin >> a;
        current_xor ^= a;  // 计算到当前位置 i 的前缀异或和

        // 步骤 A: 尝试以当前位置 i 作为区间的结尾
        // 我们需要找一个之前的断点 j-1，使得 pre[j-1] ^ pre[i] == k
        // 即 pre[j-1] == pre[i] ^ k
        int target = current_xor ^ k;

        // 如果之前存在某个位置的前缀异或和等于 target
        if (max_dp[target] != -1) {
            // 尝试以当前位置为结尾构成一个新区间
            // dp[i] = max(dp[i-1], max_dp[target] + 1)
            // 注意：这里的 dp 变量实际上在迭代过程中一方面代表
            // dp[i-1]，更新后代表 dp[i] 因为 dp[i] 至少是
            // dp[i-1]，所以直接比较即可
            dp = std::max(dp, max_dp[target] + 1);
        }

        // 更新当前前缀异或值的最大 dp 值
        // 如果当前 dp 值比之前记录的更大，则更新
        if (dp > max_dp[current_xor]) {
            max_dp[current_xor] = dp;
        }
    }

    std::cout << dp << std::endl;

    return 0;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
“luogu-”系列题目可在 洛谷题库 在线评测。
“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号

最后更新于 2026年2月4日

2025真题 | 座位 luogu-P14358