【每日一题】小AA的数列

Description

小AA找到了一个数列，她想要知道这个数列中所有长度为偶数的区间异或和之和。
后来她发现这个问题太简单了，于是她加了一个限制，要求区间长度在[L,R]之间，
然后她就不会了。。。
请你告诉她问题的答案。

Solution

异或问题优先考虑二进制位，对于这个问题，我们需要考虑偶数长度的区间，那么先对 $[L, R]$ 做处理，因为如果 $L$ , $R$ 是奇数其实加一/减一没有区别。然后处理一下前缀异或和, 因为我们有性质 $sum[l, r] = sum[r] \oplus sum[l - 1]$ 。最后我们要找到哪些是有贡献的，我们考虑枚举右端点，如果当前点的异或是 1，那么需要在前面找异或为 0 的点才有贡献，反之如果当前点的异或是 0，那么要在前面找异或为 1 的点才有贡献，此外，奇数下标要找奇数下标，偶数下标要找偶数下标，才能构成偶数长度区间。
所以我们可以用 dp[i][j] 维护前面符合条件的状态数，第一维表示当前位为 0/1, 第二维表示当前下标为奇/偶的状态数，直接计算贡献即可。

Code

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e6 + 5;
const int mod = 1e9 + 7;

int a[N];

int main() {
  int n, l, r;
  cin >> n >> l >> r;
  for(int i = 1; i <= n; i++) {
    cin >> a[i];
    a[i] ^= a[i - 1];
  }
  if(l & 1) l++; // 保证偶数长度
  if(r & 1) r--;
  if(l > r) {
    cout << 0 << "\n";
    return 0;
  }
  ll ans = 0;
  for(int i = 0; i < 32; i++) {
    ll p = (1LL << i);
    ll dp[2][2] = {0};
    ll num = 0;
    for(int j = l; j <= n; j++) {
      dp[(a[j - l] >> i) & 1][(j - l) & 1]++;
      num += dp[((a[j] >> i) & 1) ^ 1][j & 1];
      num %= mod;
      if(j >= r) {
        dp[(a[j - r] >> i) & 1][(j - r) & 1]--;
      }
    }
    ans += num * p % mod;
    ans %= mod;
  }
  cout << ans << "\n";
  return 0;
}