NC14414 小AA的数列

题目地址：

https://ac.nowcoder.com/acm/problem/14414

基本思路：

首先我们发现这是一个区间位运算的题，所以依照惯有套路，我们对于每一个二进制位分位考虑，我们发现每一位的贡献次数应该等于异或值为1且符合条件的区间的数目，然后因为对于每一位我们要找区间异或值，所以这一部分可以再使用区间异或前缀和来搞一下，然后我们还发现要考虑奇偶的情况，所以我们再对奇偶位置分别考虑分开计算就是了。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF (int)1e18

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

const int maxn = 1e5 + 10;
int n,l,r,a[maxn];
const int mod = 1e9 + 7;
int memo[2][2];
signed main() {
  IO;
  cin >> n >> l >> r;
  if (l & 1) l++; if (r & 1) r--;
  if( l==r && l&1 ){ cout<<0;return 0; }//特殊情况判断一下;
  rep(i, 1, n) {
    cin >> a[i];
    a[i] ^= a[i - 1];//整体求异或前缀和,和每一位求意思一样;
  }
  int ans = 0;
  rep(i, 0, 31) {
    mset(memo, 0);
    rep(j, 1, n) {//右端点位置;
      //在[l,r]范围内求异或前缀和;
      if (j >= l) memo[j & 1][(a[j - l] >> i) & 1]++;//范围内加;
      //同奇或同偶则长度为偶数，且异或为1则有贡献;
      ans = (ans + memo[j & 1][(a[j] >> i) & 1 ^ 1] * (1 << i) % mod) % mod;
      if (j >= r) memo[j & 1][(a[j - r] >> i) & 1]--;//超出范围减;
    }
  }
  cout << ans % mod << '\n';
  return 0;
}