异或和（xor）

本题为 CSP-J 2025 第二轮真题。本 OJ 采用标准输入输出评测，无需文件重定向。

【题目描述】 小R 有一个长度为n 的非负整数序列a1, a2, . . . , an。定义一个区间[l, r] (1 ≤l ≤ r ≤n) 的权值为al, al+1, . . . , ar 的二进制按位异或和，即al ⊕al+1 ⊕· · · ⊕ar，其中⊕表 示二进制按位异或。 小X 给了小R 一个非负整数k。小X 希望小R 选择序列中尽可能多的.不.相.交的 区间，使得每个区间的权值均为k。两个区间[l1, r1], [l2, r2] 相交当且仅当两个区间同时 包含至少一个相同的下标，即存在1 ≤i ≤n 使得l1 ≤i ≤r1 且l2 ≤i ≤r2。 例如，对于序列[2, 1, 0, 3]，若k = 2，则小R 可以选择区间[1, 1] 和区间[2, 4]，权 值分别为2 和1 ⊕0 ⊕3 = 2；若k = 3，则小R 可以选择区间[1, 2] 和区间[4, 4]，权值 分别为1 ⊕2 = 3 和3。 你需要帮助小R 求出他能选出的区间数量的最大值。 【输入格式】 从文件xor.in 中读入数据。 输入的第一行包含两个非负整数n, k，分别表示小R 的序列长度和小X 给小R 的 非负整数。 输入的第二行包含n 个非负整数a1, a2, . . . , an，表示小R 的序列。 【输出格式】 输出到文件xor.out 中。 输出一行一个非负整数，表示小R 能选出的区间数量的最大值。 【样例1 输入】 1 4 2 2 2 1 0 3 【样例1 输出】 1 2 【样例1 解释】 小R 可以选择区间[1, 1] 和区间[2, 4]，异或和分别为2 和1 ⊕0 ⊕3 = 2。可以证 明，小R 能选出的区间数量的最大值为2。 【样例2 输入】 1 4 3 2 2 1 0 3 【样例2 输出】 1 2 【样例2 解释】 小R 可以选择区间[1, 2] 和区间[4, 4]，异或和分别为1 ⊕2 = 3 和3。可以证明，小 R 能选出的区间数量的最大值为2。 【样例3 输入】 1 4 0 2 2 1 0 3 【样例3 输出】 1 1 【样例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 ≤n ≤5 × 105，0 ≤k < 220； • 对于所有1 ≤i ≤n，均有0 ≤ai < 220。 测试点编号 n ≤ k 特殊性质 1 2 = 0 A 2 10 ≤1 B 3 102 = 0 A 4, 5 ≤1 B 6 ∼8 ≤255 C 9, 10 103 11, 12 < 220 无 13 2 × 105 ≤1 B 14, 15 ≤255 C 16 < 220 无 17 5 × 105 ≤255 C 18 ∼20 < 220 无 特殊性质A：对于所有1 ≤i ≤n，均有ai = 1。 特殊性质B：对于所有1 ≤i ≤n，均有0 ≤ai ≤1。 特殊性质C：对于所有1 ≤i ≤n，均有0 ≤ai ≤255。

多边形（polygon） 多边形（polygon）

📦 本题含官方测试数据（CC BY-NC，noi.cn 发布），共 12 个测试点。