【题解】小AA的数列

感想：
真的不会做这种题，虽然已经想到了异或和这种题要按位求贡献，但是偶数还有区间这个问题想不出来怎么解决。后来看了别人的题解，想了好久才终于想明白怎么一回事了。

思路：
首先，一般异或和这种题都是按位求贡献这个方向是没错的。此时要算一个区间内的异或和的这一位是否有贡献（也就是区间异或和的这一位是否为1）可以通过异或前缀和来O(1)得到。
什么意思呢？首先我们先求一个异或前缀和，假设是sum数组，那么如果知道这个区间内异或和的这一位是否为1，只需要看sum[l-1]^sum[r]是不是1就好了。
为什么？假如sum[l-1]这一段前缀和是这一位是1，sum[r]这一位是0，那么说明在l到r这一段异或和肯定是1，因为1要和1做异或运算才能变为0。因此可以发现判断区间的某一位异或和是否为1可以通过前缀和来解决。
然后就是偶数区间怎么解决了，这个比较简单，只需要判断左右端点是不是同为奇数或者偶数就好了。
l,r就是加一个限制就好了。
然后开始算法部分：
我们维护一个dp[k][j]数组，枚举第i位，k表示所有的左端点-1中的第i位前缀和为1/0，并且j表示位置为奇数/偶数的个数。（为什么是左端点-1，因为sum[l-1]^sum[r]，上面已经说过了）
因为区间至少是[l,r]，所以我们枚举右端点从l开始，更新dp数组(假设枚举的点为j)：
dp[(a[j-l]>>i)&1][(j-l)&1]++;
表示：左端点-1这一位的前缀和是不是1，并且它的位置是奇数还是偶数。
对于这个右端点，它做的贡献就是：
dp[((a[j]>>i)&1)^1][j&1]*(1<<i)
表示它跟左端点-1这一位的前缀和异或是1（比如右端点是1，那它需要左端点-1的点是0才行，反之亦然）并且位置都是奇数/偶数的点能做2^i的贡献。
最后如果超过r了，要把数量减一下，因为不减的话求出来的区间长度就超过r了。

代码：

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<map>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
#define eps 1e-7 
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;

const int maxn=5e5+6;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;

ll dp[2][2];

ll a[maxn];

int main(){
    int n,l,r;
    scanf("%d%d%d",&n,&l,&r);
    for(int i=1;i<=n;i++){
        scanf("%d",a+i);
        a[i]=a[i-1]^a[i];
    }
    if(l&1) l++;
    if(r&1) r--;
    if(l>r){
        printf("0");return 0;
    }
    ll ans=0;
    for(int i=0;i<32;i++){
        ll tmp=(1ll<<i);
        memset(dp,0,sizeof(dp));
        ll num=0;
        for(int j=l;j<=n;j++){
            dp[(a[j-l]>>i)&1][(j-l)&1]++;
            num=(num+dp[((a[j]>>i)&1)^1][j&1])%mod;
            if(j>=r) dp[(a[j-r]>>i)&1][(j-r)&1]--;
        }
        ans=(ans+num*tmp%mod)%mod;
    }
    printf("%lld",ans);
    return 0;
}