题意

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

分析

和位运算有关的题统统按位考虑=。=，于是我们枚举二进制的每一位。
问题转化为：有 个数，每个数为 或 ，求偶数长度且长度在 且区间和为奇数的区间数量。（真tm绕）
如果区间和为奇数，意味着 。于是我们只关心前缀和的奇偶性。
这样子问题又转化另一个问题：求 中与 不同的数的个数。这个可以用一个前缀和快速求出。
然后由于区间长度为偶数，我们要对奇偶分别开一个数组记录前缀和。。细节还是挺多的。。
最后复杂度是 。

代码如下

#include <bits/stdc++.h>
#define N 100005
const int mod = 1e9 + 7;
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
LL z = 1;
int read(){
    int x, f = 1;
    char ch;
    while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
    x = ch - '0';
    while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
    return x * f;
}
int ksm(int a, int b, int p){
    int s = 1;
    while(b){
        if(b & 1) s = z * s * a % p;
        a = z * a * a % p;
        b >>= 1;
    }
    return s;
}
int a[N], s[N], sum[N][2][2];
int main(){
    int i, j, n, m, l, r, t = 1, ans = 0, tot, x, y;
    n = read(); l = read(); r = read();
    for(i = 1; i <= n; i++) a[i] = read();
    for(i = 0; i <= 30; i++){
        tot = 0;
        for(j = 1; j <= n; j++){
            if(1 << i & a[j]) s[j] = (s[j - 1] + 1) % 2;
            else s[j] = s[j - 1]; 
        }
        sum[0][0][0] = 1;
        for(j = 1; j <= n; j++){
            sum[j][0][0] = sum[j - 1][0][0]; sum[j][0][1] = sum[j - 1][0][1];
            sum[j][1][0] = sum[j - 1][1][0]; sum[j][1][1] = sum[j - 1][1][1];
            if(j >= l){
                x = max(0, j - r); y = j - l;
                if(x >= 1) tot = (tot + sum[y][j & 1][1 - s[j]] - sum[x - 1][j & 1][1 - s[j]]) % mod;
                else tot = (tot + sum[y][j & 1][1 - s[j]]) % mod;
            }
            sum[j][j & 1][s[j]]++;
        }
        ans = (ans + z * t * tot) % mod;
        t = t * 2 % mod;
    }
    printf("%d", (ans + mod) % mod);
    return 0;
}