首页 > 试题广场 >

子段异或

[编程题]子段异或

热度指数：8 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

输入一个数列a，你需要输出其中异或值为0的不同子段的数量。一个子段 [l,r] ( $1 \le l \le r \le n$ )的异或值为 $a_l \oplus a_{l+1} \oplus a_{l+2} \oplus \ldots\oplus a_r$ ，其中 $\oplus$ 符号代表异或运算。

两个子段被视为相同的，当且仅当其开始和结束位置均对应相同。

输入描述:

第一行一个整数 n ，代表数列长度。
第二行 n 个整数，代表数列。

输出描述:

输出一个整数，代表答案。

示例1

输入

5
1 2 3 2 1

输出

说明

子段 [1,3] 和子段 [3,5] 是合法子段。

备注:

算法知识视频讲解

998244353

发表于 2020-02-12 12:31:46

看到区间异或和就想起来了前缀。前置知识：(下面的[xx,yy]代表从xx到yy的异或和) 所以有：所以预处理出所有的前缀异或和即可，由于需要，故这里可不用map，直接sort一遍即可使得相同的值相邻，然后记录这种区间的个数。由于要在所有异或和相同的区间中选择两个区间，贡献即：，遍历一遍即可展开全文

QQQQwQQQQ

发表于 2020-02-11 21:40:48

子段异或https://ac.nowcoder.com/acm/contest/3005/D 亦或运算中连续一段的运算 a[0]^...a[i]^a[i+1]^...^a[i+k]^...^a[n] 中若出现相同的亦或前缀和，如a[0]^...^a[i]的亦或前缀和与 a[0]^...^a[i+ 展开全文