小AA的数列

见一次忘一次,见到求异或和之和的全部转换为二进制,然后判断 有多少种组合
既然要求长度在[L,R]之间偶数的异或和之和,那啥都别说先来求一个前缀异或和,然后我们可以想一下下来暴力的求解怎么做
比如枚举[L,R]之间偶数为长度,然后一遍一遍的过数组......铁定超时
异或的性质
所以
做这种题有一个东西就是,把其转换为二进制,举个例子: 0到L-1和0到R的前缀异或和分别为5和10,那么 ,
0101--->5
1001--->9
1100--->12
所以我们要求异或和之和就是相当于找其中二进制下相同位能找到多少满足要求的
长度为偶数就是L和R同为奇数,或者同为偶数
所以我们可以枚举每个点为右边界,然后统计到当前点是偶数的点存在多少0或1,和奇数的点存在多少0或1
枚举二进制下的1-32,即每个前缀异或和在二进制下当前位的值为0/1

当前位置的异或和的值为0/1,当前位置的点是奇数还是偶数
然后对于求出来的当前位置找到的 的个数乘以
然后再加上答案取余
时间复杂度:
求异或和之和,即异或前缀和转二进制求可能的情况个数

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=1e9+7;
int a[100009],n,L,R;
int dp[2][2];
int main(){
    scanf("%d%d%d",&n,&L,&R);
    if(L==R)
    {cout<<0;return 0;}
    if(L&1) L++;//保证最长区间为偶数
    if(R&1) R--;
    a[0]=0;
    int tmp;
    for(int i=1;i<=n;i++){
        scanf("%d",&tmp);
        a[i]=a[i-1]^tmp;
    }
    ll ans=0;
    for(int i=0;i<32;i++){
        memset(dp,0,sizeof(dp));
        ll sum=0;
        ll tmp=1<<i;
        for(int j=L;j<=n;j++){
            dp[(a[j-L]>>i)&1][(j-L)&1]++;//当前位是0/1,当前j是奇数还是偶数
            sum+=dp[((a[j]>>i)&1)^1][j&1];
            if(j>=R) dp[(a[j-R]>>i)&1][(j-R)&1]--;//区间越界
        }
        ans=(ans+tmp*sum%mod)%mod;
    }
    printf("%lld\n",ans);
    return 0;
}