题意:


给定一个数列,找出这个数列中长度为偶数的连续子列的异或和
并且要求长度为偶数的同时满足在之间
最后结果


思路:


异或一般是是枚举每一个数每个二进制位的贡献
1.这道题需要考虑的是一个连续子列,我们可以维护一个前缀和

cin>>a[i],a[i]^=a[i-1];

2.那么枚举每个前缀的二进制位,看在某一个二进制位上这个前缀前面的个前缀有多少个是与他相反的前缀,然后每一二进制位综合起来乘上权值就可以算出来不考虑偶数限制的结果。

c[(a[j]>>i)&1^1]*(1ll<<i)//不考虑偶数限制,也就是不考虑第一维

表示右端点到左端点+1这个点(其实是区间的贡献,我们枚举的是右端点然后取有贡献的左端点,左端点的范围是)的前缀和异或是1(比如右端点是1,那它需要左端点-1的点是0才行,反之亦然)能做的贡献。
比如(假设只有一位):

下标:  1 2 3 4 5 6 7

原数组:1 0 1 1 0 0 1    a[1~7]
前缀和:1 1 0 1 1 1 0    b[1~7]指的是前缀异或和

枚举右区间为,此时表示和异或为1的前缀个数(也就是有贡献的左端点个数),也就是说,表示区间异或为1。
3.然后,考虑一下偶数的限制,奇数减奇数和偶数减偶数是偶数。所以在存某一个二进制位上这个前缀前面的个前缀有多少个是与他相反的前缀时区分下标的奇偶。

++c[j&1][(a[j-l]>>i)&1];//[j-l]里面的l是小写字母,看了我一天

4.最后解决一下,的限制
右端点枚举到才开始存左端点,当右端点大于等于时开始维护区间长度,即减去最先存进来的左端点,保证区间长度不大于

--c[j&1][(a[j-r]>>i)&1];

5.每一位的贡献就是存进来的左端点和枚举右端点这一位的数值不同的个数乘以这一位的权值。

c[j&1][(a[j]>>i)&1^1]*(1ll<<i)

6.还有一个比较直接的问题,题目没有限定一定为偶数,如果区间里只有奇数,即并且为奇数那么结果肯定是0,还有如果为奇数的时候,但不可能出现奇数,所以往中间减少一下。


Code:


#include<bits/stdc++.h>
#define  js  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int maxn=1e6+10;
ll c[2][2],a[maxn];
int main() {
    int n,l,r; js;
    cin>>n>>l>>r;
    if(l==r&&l&1) {
        cout<<0; return 0;
    }
    if(l&1)l++; if(r&1)r--;
    for(int i=1;i<=n;i++)cin>>a[i],a[i]^=a[i-1];
    ll ans=0;
    for(int i=0;i<=31;i++){
        memset(c,0,sizeof c);
        for(int j=l;j<r;j++){
            ++c[j&1][(a[j-l]>>i)&1];
            ans=(ans+c[j&1][(a[j]>>i)&1^1]*(1ll<<i)%mod)%mod;
        }
        for(int j=r;j<=n;j++){
            ++c[j&1][(a[j-l]>>i)&1];
            ans=(ans+c[j&1][(a[j]>>i)&1^1]*(1ll<<i)%mod)%mod;
            --c[j&1][(a[j-r]>>i)&1];
        }
    }
    cout<<ans<<"\n";
    return 0;
}