题目背景

CSP-J2025 T3

题目描述

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

输入输出样例

4 2
2 1 0 3

2

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

4 2
2 1 0 3

2

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

4 0
2 1 0 3

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×10⁵，0≤k<2²⁰； •对于所有1≤i≤n，均有0≤ai<2²⁰。

特殊性质A：对于所有1≤i≤n，均有ai=1。 特殊性质B：对于所有1≤i≤n，均有0≤ai≤1。 特殊性质C：对于所有1≤i≤n，均有0≤ai≤255。