2 条题解
-
0
首先先写一个异或前缀和数组的预处理,这个问题求区间实际上可以用i和j枚举所有开始和结尾,然后利用[l,r]区间的异或前缀和为s[r]^s[l-1]来暴力,但是复杂度是n方。换一种思路,这里利用一下异或的性质,我们要求s[r]^s[l-1]=x的情况,这实际上等价于求s[r]^x=s[l-1],这是异或运算的性质,那么我们可以枚举所有可能的s[l-1],储存其值和出现的次数l-1的取值范围实际上就是0到r-1,最后统计有多少匹配的并加和即可。
import sys input = lambda:sys.stdin.readline().strip() n, x = map(int, input().split()) a = [0] + list(map(int, input().split())) s = [0] * (n + 1) for i in range(1, n + 1): s[i] = s[i-1] ^ a[i] from collections import defaultdict count = defaultdict(int) ans = 0 for r in range(1, n + 1): count[s[r-1]] += 1 tar = s[r] ^ x if tar in count: ans += count[tar] print(ans)
信息
- ID
- 456
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- 递交数
- 133
- 已通过
- 35
- 上传者