小AA的数列

题意：给出一个长度为n的序列，要求区间长度在[L,R]之间且为偶数的区间异或和之和？

思路：参考：https://blog.nowcoder.net/n/4dacd8e372de4199a30442b4eee1849a
sum[i][j]为前i个数在第j位为1的个数
pre[i][j][0]为在sum[k][j] (k<=i&&k>=1&&ki mod(2) )中为偶数的个数
pre[i][j][1]为在sum[k][j] (k<=i&&k>=1&&ki mod(2) )中为奇数的个数
结果等于每一位在规定区间长度内为偶数的区间的数目为奇数的区间数乘以位权之和

代码：

#include<bits/stdc++.h>
#define ll long long
#define inf 1000000007

using namespace std;

int n, l, r, a[100005], sum[100005][31], pre[100005][31][2];
ll ans=0;

void solve()
{
    for(int i=1; i<=n; i++)
    {
        for(int j=0; j<31; j++)
        {
            sum[i][j]=sum[i-1][j]+((a[i]>>j)&1);
            if(i!=1)
            {
                pre[i][j][0]=pre[i-2][j][0];
                pre[i][j][1]=pre[i-2][j][1];
            }
            pre[i][j][sum[i][j]%2]++;
            //printf("%d ",pre[i][j][1]);
        }
        //printf("\n");
    }
    for(int i=1; i<=n-l+1; i++)
    {
        int l1=i+l-1, r1=min(i+r-1,n);
        if(l%2==1)
        {
            l1++;
        }
        if((r1-i+1)%2==1)
        {
            r1--;
        }
        if(l1>r1)
        {
            continue;
        }
        for(int j=0; j<31; j++)
        {
            if(l1>1)
                ans=(ans+(1LL<<j)%inf*(pre[r1][j][1-sum[i-1][j]%2]-pre[l1-2][j][1-sum[i-1][j]%2])%inf)%inf;
            else
                ans=(ans+(1LL<<j)%inf*pre[r1][j][1-sum[i-1][j]%2]%inf)%inf;
        }
    }
}

int main()
{
    scanf("%d%d%d",&n,&l,&r);
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);
    }
    solve();
    cout << ans << endl;
    return 0;
}