【题目来源】
蓝桥云课：1.异或森林 - 蓝桥云课 (lanqiao.cn)
【题目描述】
在一个神秘的世界中，存在着一个称为"异或森林"的地方。异或森林中的每个树木都拥有独特的力量。肖恩进入了这片森林，他得到了一个任务：找出数组中满足条件的连续子数组，使得连续子数组中所有元素异或运算结果的因数个数为偶数。完成任务将揭示宝藏的所在地。现在，你能告诉肖恩有多少个连续子数组满足条件吗?
注意：\(0\) 的因数个数视为奇数。
【输入】
第一行输入一个数字 \(n\) 表示数组元素个数。
第二行输入 \(n\) 个数字， 第 \(i\) 个数字 \(a[i]\) 表示数组的第 \(i\) 个元素。
【输出】
输出一个数字表示满足条件的连续子数组的数量。
【输入样例】
5
1 2 3 4 5
【输出样例】
7
【算法标签】
《蓝桥云课 3400 异或森林》 #思维# #二进制#
【代码详解】
#给定一个长度为n的数字列表，求有多少个子数组满足：
#子数组元素异或结果不是平方数 = 所有子数组 - 子数组元素异或结果是平方数
#题目转换成：求有多少个子数组异或结果是平方数
#(a[1]^a[2]^...^a[l-1]^a[l]^...^a[r])^(a[1]^a[2]^...^a[l-1)
#pre_xor[r] ^ pre_xor[l-1] = a[l]^...^a[r]
#题目转换成：求有多少个二元组<l,r>满足pre_xor[r] ^ pre_xor[l-1]是平方数
#从小到大枚举所有平方数x，求有多少个二元组<l,r>满足pre_xor[r] ^ pre_xor[l-1] = x
#pre_xor[l-1] = x ^ pre_xor[r]
#对于每一个r，找出左边有多少个值等于x ^ pre_xor[r]n = int(input())
a = list(map(int, input().split()))
#预处理前缀异或
pre_xor = [0]*n
pre_xor[0] = a[0]
for i in range(1, n):pre_xor[i] = pre_xor[i-1] ^ a[i]#ans表示子数组元素异或结果是平方数的个数
ans = 0
#从小到大枚举所有的平方数
for i in range(200):x = i*i#字典维护的是pre_xor中每个数字出现的次数dic = {}#最开始pre_xor[-1]=0，即0出现了1次dic[0] = 1for r in range(n):ans += dic.get(x ^ pre_xor[r], 0)dic[pre_xor[r]] = dic.get(pre_xor[r], 0) + 1#ans表示子数组异或结果是非平方数的个数
ans = n * (n+1) // 2 - ans
print(ans)
【运行结果】
5
1 2 3 4 5
7