Dotcpp  /  编程题库  /  [CSP-J 2025] 3. 异或和
题目 1806:

[CSP-J 2025] 3. 异或和

 时间限制: 1s 内存限制: 128MB
题目描述

小 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 求出他能选出的区间数量的最大值。

输入格式

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

输入的第二行包含 n 个非负整数 a1,a2,…,an，表示小 R 的序列。

输出格式

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


输入

4 2

2 1 0 3


输出

2

样例输入

4 3
2 1 0 3

样例输出

2
提示

【样例 1 解释】

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

【样例 2 解释】

小 R 可以选择区间 [1,2] 和区间 [4,4]，异或和分别为 1⊕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 的约束条件。

360截图20251214142004583.jpg

通过率

统　计

暂无提交数据

　提交 0
　正确 0
　格式错误 0
　答案错误 0
　时间超限 0
　内存超限 0
　输出超限 0
　运行错误 0
　编译错误 0