每日一题 5月25日 NC14414 小AA的数列 按位异或计算区间贡献

题目链接：https://ac.nowcoder.com/acm/problem/14414

#include <bits/stdc++.h>
#define LL long long
using namespace std;

const int mod=1e9+7;
int n, L, R, a[100005];
int sum[100005], cut[100005][2];
//cut[i][0]; i i-2 i-4 ... 的x位为1前缀和为偶数的个数
//cut[i][1]; i i-2 i-4 ... 的x位为1前缀和为奇数的个数
LL slove(int x){
    for(int i=1; i<=n; i++){
        sum[i]=sum[i-1]+((a[i]>>x)&1);
    }
    cut[1][1]=(sum[1]%2==1); cut[1][0]=(sum[1]%2==0);
    for(int i=2; i<=n; i++){
        cut[i][0]=cut[i-2][0]+(sum[i]%2==0);
        cut[i][1]=cut[i-2][1]+(sum[i]%2==1);
    }
    LL ans=0;
    for(int i=1; i<=n; i++){

        //范围区间缩小
        int l=i+L-1, r=min(i+R-1, n);
        if(i%2==l%2){
            l++;
        }
        if(i%2==r%2){
            r--;
        }
        if(l>r) continue;
        LL nowsum=sum[i-1];
        if(nowsum%2==1){
            ans=ans+=cut[r][0]-cut[l-2][0];
        }
        else{
            ans=ans+=cut[r][1]-cut[l-2][1];
        }
        ans%=mod;
    }
    return ans;
}

int main(){
    scanf("%d%d%d", &n, &L, &R);
    for(int i=1; i<=n; i++){
        scanf("%d", &a[i]);
    }
    LL ans=0;
    for(int i=0; i<=30; i++){
        ans=(ans+slove(i)*((1ll<<i)%mod)%mod)%mod;
    }
    printf("%lld\n", ans);

    return 0;
}