#1431. [CSP-J 2025] 异或和

[CSP-J 2025] 异或和

题目描述

小 R 有一个长度为 nn 的非负整数序列 a1,a2,…,ana_1, a_2, \dots, a_n。定义一个区间 [l,r][l, r] (1≤l≤r≤n1 \leq l \leq r \leq n) 的权值为 al,al+1,…,ara_l, a_{l+1}, \dots, a_r 的二进制按位异或和,即 al⊕al+1⊕⋯⊕ara_l \oplus a_{l+1} \oplus \dots \oplus a_r,其中 ⊕\oplus 表示二进制按位异或。

小 X 给了小 R 一个非负整数 kk。小 X 希望小 R 选择序列中尽可能多的不相交的区间,使得每个区间的权值均为 kk。两个区间 [l1,r1],[l2,r2][l_1, r_1], [l_2, r_2] 相交当且仅当两个区间同时包含至少一个相同的下标,即存在 1≤i≤n1 \leq i \leq n 使得 l1≤i≤r1l_1 \leq i \leq r_1 且 l2≤i≤r2l_2 \leq i \leq r_2。

例如,对于序列 [2,1,0,3][2, 1, 0, 3],若 k=2k = 2,则小 R 可以选择区间 [1,1][1, 1] 和区间 [2,4][2, 4],权值分别为 22 和 1⊕0⊕3=21 \oplus 0 \oplus 3 = 2;若 k=3k = 3,则小 R 可以选择区间 [1,2][1, 2] 和区间 [4,4][4, 4],权值分别为 1⊕2=31 \oplus 2 = 3 和 33。

你需要帮助小 R 求出他能选出的区间数量的最大值。

输入格式

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

输入的第二行包含 nn 个非负整数 a1,a2,…,ana_1, a_2, \dots, a_n,表示小 R 的序列。

输出格式

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

样例

4 2
2 1 0 3
2
4 3
2 1 0 3
2
4 0
2 1 0 3
1

题目来源:洛谷 P14359