【每日一题】5月25日题目精讲

题号 NC14414
名称 小AA的数列
来源 Wannafly挑战赛4
戳我进入往期每日一题汇总贴~
往期每日一题题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情

题解

异或有一个很快乐的一点就是，异或零什么都不会发生，异或偶数个1是0，异或奇数个1是1，于是我们就可以按位计算1的个数（奇偶性）了。
目标是求区间异或之和，所以我们考虑统计前缀，即前i个数中每一位为1的个数，然后算出所有符合条件的子区间当前位有多少个1就行了。（这是套路啊套路）
先不考虑区间长度为偶数这个限制：
显然枚举区间两个端点要超时，我们看能不能只枚举一个端点：
（具体分析问题的时候只需要考虑第x位，x相当于一个循环变量）
先枚举左端点l，每个和他1的个数的前缀和奇偶性不同的右端点，都会对答案有的贡献（在第x位贡献一个1）。
所以用一个数组cnt[j][0/1]来统计前缀和sum的第j个后缀（sum[j]到sum[n]）里面1的个数为奇数/偶数的个数就行。
题面要求区间长度必须为偶数怎么办？
cnt[j]计算的时候不要从cnt[j+1]来，从cnt[j+2]来，即跳过会让区间长度变成奇数的点，这样就可以啦。

看完邓老师的题解，记得自己去做题提高呀~
欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目6月1日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴