【每日一题】小AA的数列
小AA的数列
https://ac.nowcoder.com/acm/problem/14414
痛苦，悲伤，贼难orz
题目描述：
小AA找到了一个数列，她想要知道这个数列中所有长度为偶数的区间异或和之和 。
后来她发现这个问题太简单了，于是她加了一个限制，要求区间长度在[L,R]之间，
然后她就不会了。。。
输入描述：
第一行三个数 n, L, R(n<=105,1<=L<=R<=n)
输出描述：
输出一行表示答案，由于答案可能很大，请输出答案模109+7的值。
题目
题目描述：小AA找到了一个数列，她想要知道这个数列中所有长度为偶数的区间异或和之和 。
后来她发现这个问题太简单了，于是她加了一个限制，要求区间长度在[L,R]之间，
然后她就不会了。。。
请你告诉她问题的答案。
第一行三个数 n, L, R(n<=105,1<=L<=R<=n)
第二行n个数表示这个数列。(ai<=109)
输出一行表示答案，由于答案可能很大，请输出答案模109+7的值。
解析
这么久以来，我一看到异或和的题目，或者是按位求贡献的题目，我就不会。。。我这次看了一天总算懂了一点orzzzz
首先我们看一下题目：
- 首先当我们看到异或和这种题目，就一定能想到前缀和。
- 然后是求异或和之和，既然是求和，我们也能想到按位求贡献。
- 然后另外这道题就是难在：长度为偶数；长度在L~R之间；
首先我们讲一下按位求贡献：
- 首先讲到按位求贡献的原理：
如果一堆数求异或，用二进制也就是每一位求异或，也就是一堆0和1求异或,0对答案是没有任何贡献的，只有1有贡献。
并且1的数量为奇数，异或值为1。如果1的数量为偶数，异或值为0（因为异或相同的为0，所以两个1就会抵消）。 - 所以在这一堆数求异或之后，结果每一位留下的数，组成十进制之后，就是这一堆数的异或值。
然后是前缀和：
- 我们用前缀和来储存前面所有数字的每一位上1的数量。（我们就是用这个方法可以O(1)地查到一段区间的异或值）
- 所以这里我们的前缀和数组为：
int sum[MAX][30];//sum的前i项（前i个数），二进制第j位上从info[1]~info[n]上的1的数量（对二进制每一位的前缀和）
根据这道题的特性，我们要求前缀和之和：
- 所以我们这里要知道有多少个前缀和（统计前缀和的个数）。
- 也就是知道我们这里有多少个可以用来求和的1（每一个前缀和都是用来保存当前的异或值，所以这里也就是在求异或和之和）。
- 这里我们就可以用一个新的数组来统计异或和中每一位的数量（没错，统计每一位，因为十进制的异或和依旧可以转换成二进制按位求值）：
int cnt[MAX][30][2];//第一维为数字表示前i项，然后是二进制第j位，0/1表示前j位sum为奇/偶的个数
- 这里要讲的就是奇偶的个数了，因为题目要求了，只能是偶数长的区间，所以在起点相同的情况下，偶数长一定是终点全奇数点或全偶数点的。
然后就要考虑长度为偶数的情况了：
- 因为长度为偶数，也就是说，每隔一个，我们才能进行一次计算。那我们自然而然也就会想到位置的奇偶性。
- 也就是我们上面在统计前缀和之和的时候所考虑到的奇偶点的情况了。
- 然后我们就可以按照我们上面讲的来初始化我们的sum和cnt数组了。
接下来就是考虑L~R的情况了，这个其实就是计算的问题，我们就在计算答案的时候判断就好了：
- 首先我们要用到外层循环遍历左端点，并确定右端点所在的区间范围的位置（用left和right标记区间两端）：
int left = i + L - 1, right = min(n, i + R - 1);//区间长为L~R，计算出区间位置 //注意一下，right可能越界，越界就自然的选n
- 这里要注意特判，区间长度可能为奇数，所以要排除这种情况：
if ((left - i + 1) & 1) left++; if ((right - i + 1) & 1) right--; //强制使区间长度变为偶数，左端点只能向右，右端点只能向左(不能跑到区间外面去了) //left - i + 1算出来就是区间长度，所以就是区间长度&1 //这里不用L和R进行判断是因为，右端点可能越界，然后选了n做右端点
- 自然而然，left和right缩小范围之后，left可能会比right要大，就不符合常理了，就不计这种情况，continue就行。
- 否则，我们就可以正常的进行计算：计算方式就是简单的对每一位求出在这个区间里面1的数量
（利用cnt数组的差值就可知道，我们上面隔一个进行统计就是为了这里），加起来就是异或和之和了。 - ————————————————————skr————————————————————
- 然后我们分步讲解一下：
- 首先，我们知道cnt里面是统计的奇数和偶数的sum的个数的，用哪个呢？就要考虑我们的起点了：我们要偶数长度，起点终点的奇偶性当然就不一样：
int v = (sum[i - 1][j] & 1) ^ 1; //v表示右端点，为了使长度为偶数长，起点(sum[i - 1][j] & 1)和终点的奇偶性不一样 //数字取反我们用^1，C/C++用！也是一样的。
- 然后我们就要用右端点和左端点取差值了：
ll tot = cnt[right][j][v] - cnt[left - 2][j][v];//计算右端点和左端点之间的差值（sum异或和为1的个数）
- 求完了数量再给他把这些东西给他放到答案的每一位上去就好了：
ans = (ans + (1 << j) * tot % MOD) % MOD;
- 如此循环统计。
总算到了打代码了：
- 首先自然就是输入我们的数据。
- 然后用这些数据将sum和cnt数组按照上面的方式进行初始化了。
- 接下来我们就按照上面讲的异或和统计将答案统计累加出来。
- 输出答案就好。
- 看我代码吧。。。代码还是很详细的orzzzz
AC代码
#include <iostream>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区
const int MOD = 1e9 + 7;
const int MAX = 1e5 + 7;
int n, L, R;
int sum[MAX][30];//sum的前i项（前i个数），二进制第j位上从info[1]~info[n]上的1的数量（对二进制每一位的前缀和）
int cnt[MAX][30][2];//第一维为数字表示前i项，然后是二进制第j位，0/1表示前j位sum为奇/偶的个数
//全局变量区
int main() {
IOS;
cin >> n >> L >> R;
for (int i = 1; i <= n; i++) {
int info; cin >> info;//输入数据
for (int j = 29; ~j; --j) {
sum[i][j] = sum[i - 1][j] + ((info >> j) & 1);
//sum第二维(二进制位)的累加，(info[i] >> j) & 1取出二进制第j位
if (i != 1) {
cnt[i][j][0] = cnt[i - 2][j][0];
cnt[i][j][1] = cnt[i - 2][j][1];
}
//本位先继承之前位的东西，之所以是i - 2是因为区间长为偶数
cnt[i][j][sum[i][j] & 1]++;
//再加上本位的情况，sum[i][j] & 1就是判断当前sum奇偶
}
}
//数组初始化
int ans = 0;
for (int i = 1; i <= n; i++) {
//外层循环枚举左端点，i为左端点
int left = i + L - 1, right = min(n, i + R - 1);//区间长为L~R，计算出区间位置
if ((left - i + 1) & 1) left++;
if ((right - i + 1) & 1) right--;
//强制使区间长度变为偶数，左端点只能向右，右端点只能向左(不能跑到区间外面去了)
//left - i + 1算出来就是区间长度，所以就是区间长度&1
//这里不用L和R进行判断是因为，右端点可能越界，然后选了n做右端点
if (left > right) continue;//特判缩小范围后越界的情况
for (int j = 29; ~j; j--) {
int v = (sum[i - 1][j] & 1) ^ 1;
//v表示右端点，为了使长度为偶数长，起点(sum[i - 1][j] & 1)和终点的奇偶性不一样
ll tot = cnt[right][j][v] - cnt[left - 2][j][v];
//计算右端点和左端点之间的差值（sum异或和为1的个数）
ans = (ans + (1 << j) * tot % MOD) % MOD;
}
}
cout << ans << endl;
return 0;
}
//函数区每日一题 文章被收录于专栏
憨憨的专栏
查看16道真题和解析
