#2109. 「CSP-J 2025」异或和 普及/提高−

小 R 有一个长度为 的非负整数序列 。定义一个区间 () 的权值为 的二进制按位异或和，即 ，其中 表示二进制按位异或。

小 X 给了小 R 一个非负整数 。小 X 希望小 R 选择序列中尽可能多的不相交的区间，使得每个区间的权值均为 。两个区间 相交当且仅当两个区间同时包含至少一个相同的下标，即存在 使得 且 。

例如，对于序列 ，若 ，则小 R 可以选择区间 和区间 ，权值分别为 和 ；若 ，则小 R 可以选择区间 和区间 ，权值分别为 和 。

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

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

输入的第二行包含 个非负整数 ，表示小 R 的序列。

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

样例输入 1

4 2
2 1 0 3

样例输出 1

2

样例解释 1

小 R 可以选择区间 和区间 ，异或和分别为 和 。可以证明，小 R 能选出的区间数量的最大值为 。

样例输入 2

4 3
2 1 0 3

样例输出 2

2

样例解释 2

小 R 可以选择区间 和区间 ，异或和分别为 和 。可以证明，小 R 能选出的区间数量的最大值为 。

样例输入 3

4 0
2 1 0 3

样例输出 3

1

样例解释 3

小 R 可以选择区间 ，异或和为 。可以证明，小 R 能选出的区间数量的最大值为 。注意：小 R 不能同时选择区间 和区间 ，因为这两个区间同时包含下标 。

样例 4

见选手目录下的 与 。

该样例满足测试点 的约束条件。

样例 5

见选手目录下的 与 。

该样例满足测试点 的约束条件。

样例 6

见选手目录下的 与 。

该样例满足测试点 的约束条件。

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

• , ;
• 对于所有 ，均有 。

特殊性质 A: 对于所有 ，均有 。

特殊性质 B: 对于所有 ，均有 。

特殊性质 C: 对于所有 ，均有 。

附件下载

xor.zip240.24KB