#cspjf2025t3. 异或和(xor)
异或和(xor)
异或和(xor)
题目描述
小 R 有一个长度为 n 的非负整数序列 。定义一个区间 的权值为 的二进制按位异或和,即 ,其中 ⊕ 表示二进制按位异或。
小 X 给了小 R 一个非负整数 k。小 X 希望小 R 选择序列中尽可能多的不相交的区间,使得每个区间的权值均为 k。两个区间 相交当且仅当两个区间同时包含至少一个相同的下标,即存在 1≤i≤n 使得 且 。
例如,对于序列 [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 个非负整数 ,表示小 R 的序列。
输出格式
输出一行一个非负整数,表示小 R 能选出的区间数量的最大值。
输入输出样例 #1
4 2
2 1 0 3
2
输入输出样例 #2
4 3
2 1 0 3
2
输入输出样例 #3
4 0
2 1 0 3
1
说明/提示
【样例 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 的约束条件。
数据规模与约定
对于所有测试数据,保证:
- ;
- 对于所有 ,均有 。
| 测试点编号 | n≤ | k | 特殊性质 |
|---|---|---|---|
| 1 | 2 | =0 | A |
| 2 | 10 | ≤1 | B |
| 3 | =0 | A | |
| 4,5 | ≤1 | B | |
| 6∼8 | ≤255 | C | |
| 9,10 | |||
| 11,12 | 无 | ||
| 13 | ≤1 | B | |
| 14,15 | ≤255 | C | |
| 16 | 无 | ||
| 17 | ≤255 | C | |
| 18∼20 | 无 |
特殊性质 A: 对于所有 ,均有。
特殊性质 B: 对于所有 ,均有。
特殊性质 C: 对于所有 ,均有。