2025 T3 异或和

主知识点：贪心。交叉标签：贪心、前缀异或、哈希、动态规划。
暴力标注：有非 DP 满分解。
OJ 使用标准输入与标准输出。原比赛文件名为 xor.in / xor.out；下方如保留原文件约定，以本句的 OJ 约定为准。
时限 1 秒；内存 512 MiB；测试点 20；总分 100。
数据来源：自制训练数据（90 点中的本题部分，非官方）。

2025 年本题评测数据为自制训练数据；下方约束表仍是原题约束。训练分数不等同于原赛成绩。

题目描述

给出非负整数序列 $a_1..a_n$ 及目标 $k$。区间权值为区间内全部数的按位异或。选择尽可能多的非空区间，使每个区间异或和等于 $k$，且任意两区间不共享下标。输出最多可以选择的区间数。

输入格式

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

输入的第二行包含 $n$ 个非负整数 $a_1, a_2, \dots, a_n$，表示小 R 的序列。

输出格式

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

样例

样例 1

输入：

4 2
2 1 0 3

输出：

2

样例 2

输入：

4 3
2 1 0 3

输出：

2

样例 3

输入：

4 0
2 1 0 3

输出：

1

数据范围与特殊性质

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

• $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$		$\leq 1$	B
$6 \sim 8$		$\leq 255$	C
$9, 10$	$10^3$
$11, 12$		$< 2^{20}$	无
$13$	$2 \times 10^5$	$\leq 1$	B
$14, 15$		$\leq 255$	C
$16$		$< 2^{20}$	无
$17$	$5 \times 10^5$	$\leq 255$	C
$18 \sim 20$		$< 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$。

附加样例

本题的公开样例整理在对应的“样例”ZIP 中。样例不计入评测测试点；题面中的样例也已保留。

暴力退路标注（教学补充）

有非 DP 满分解。最早结束的合法区间贪心即可满分。也可枚举每个结尾与起点计算异或，并做区间 DP，O(n²) 面向 n≤1000 的 1~12 点；这是朴素 DP，并非纯 DFS。

目标范围：非 DP 贪心满分；O(n²) DP 面向前 60%。部分分按原题规模判断，不构成对任意实现或评测机的得分保证。

来源与整理说明

题目原作者/发布者：中国计算机学会 CCF / NOI。题意经过改写，保留公式、输入输出、样例及约束；知识点和暴力标注为本次整理补充。

• 题面及约束校对来源：洛谷 CCF_NOI 题目 P14359
• 赛事：CSP-J 第二轮入门级 2025。
• 详细数据来源、版本和哈希见总包 来源与校验/manifest.json。