2 条题解

  • 0
    @ 2026-3-9 16:03:09

    首先先写一个异或前缀和数组的预处理,这个问题求区间实际上可以用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
    上传者