小AA的数列

题解：

很套路的一道题：由于所求的是异或之和，我们知道位运算不产生进位，所以每个数位与位之间的贡献是独立的，不想不影响，那么我们考虑按位计算对 答案的贡献即可，
令pre[i][j]表示 前i个数中第j位为1的个数，那么当我们枚举所有区间的左端点i时，如果pre[i-1][j]是奇数，那么所有能对答案造成贡献的右端点r的pre[r][j]一定是偶数，反之亦然。
所以，我们在令cnt[i][j]表示前i个数中,pre[i][j]为奇数的个数，但是题目还有一个限制条件就是长度必须是偶数，所以我们把cnt[i][j]表示前面与i奇偶性相同的个数，
这样，当我们枚举所有区间的左端点i时，就可以O1的计算答案了~

代码：

#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
#define fi first
#define se second
#define pb push_back
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const  ll inf  = 0x3f3f3f3f3f3f3f3f;
const int mod  = 1e9+7;
const int maxn = 1e5 + 4;
const int N    = 5e3 + 5;
const double eps = 1e-6;
const double pi = acos(-1);
ll qpow(ll x,ll y){ll ans=1;x%=mod;while(y){ if(y&1) ans=ans*x%mod; x=x*x%mod; y>>=1;}return ans;}


int n,l,r,pre[maxn][31],cnt[maxn][31],a[maxn];
ll ans;
int main(){
    //freopen("input.in","r",stdin);
    scanf("%d%d%d",&n,&l,&r);
    for(int i=1;i<=n;i++) {
        scanf("%d",&a[i]);
        for(int j=0;j<=30;j++) {
            pre[i][j]=(a[i]>>j)&1;
        }
        for(int j=0;j<=30;j++) {
            pre[i][j]+=pre[i-1][j];
            cnt[i][j]=pre[i][j]&1;
        }
        for(int j=0;j<=30;j++) {
            if(i>1) cnt[i][j]+=cnt[i-2][j];
        }
    }
    for(int i=1;i+l-1<=n;i++) {
        int L=i+l-1,R=min(n,i+r-1);
        if((L-i+1)&1) L++;
        if((R-i+1)&1) R--;
        if(L>R) continue;

        for(int j=0;j<=30;j++) {
            ll k=cnt[R][j]-cnt[max(0,L-2)][j];
            if(pre[i-1][j]&1) ans+=1ll*((R-L+2)/2-k)*(1<<j)%mod;
            else ans+=k*(1<<j)%mod;
            //cout<<i<<','<<j<<','<<k<<endl;
            ans%=mod;
        }
        //cout<<ans<<endl;
    }
    printf("%lld\n",ans);
}