【每日一题】5月25日 小AA的数列

题目大意：
小AA找到了一个数列，她想要知道这个数列中所有长度为偶数的区间异或和之和 。
后来她发现这个问题太简单了，于是她加了一个限制，要求区间长度在[L,R]之间，

参考wxyww的优美代码.

https://blog.nowcoder.net/n/b1816a1594eb41389e78659f45467d06

分析：异或和题目经典套路按二进制位进行计算。
对每一个数进行二进制拆分，然后每一位依次做前缀和。 表示前i个长度为偶数的前缀区间异或值为j的个数是多少。
并且由于区间长度必须是偶数，那么做前缀和的时候 应该由 进行转移累加.
一个非常优美的实现就是前缀和从下标 开始进行。
那么对于当前第 位置。
如果前缀异或和为1， 以当前为右区间的有贡献的合法偶数长度区间的方案数是
.
如果前缀异或和为0， 以当前为右区间的有贡献的合法偶数长度区间的方案数是
.
最后方案数乘以二进制下第i位数为1 的十进制大小。所有位数贡献累加起来就是答案。

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

const int mod=1e9+7;
typedef long long ll;
const int maxn=1e5+10;
int sum[maxn][2],a[maxn],n,l,r;

ll solve( int x )
{
    sum[n][0]=1;
    for( int i=1;i<=n;i++ )
    {
        sum[i+n][0]=sum[i+n-2][0]+( ( a[i]>>x & 1 )^1 );
        sum[i+n][1]=sum[i+n-2][1]+( a[i]>>x & 1 );
    }
    ll res=0;
    for( int i=1;i<=n;i++ )
    {
        int R=i-l,L=i-r-2;
        if( a[i]>>x&1 ) res+=max(0,sum[R+n][0]-sum[L+n][0]);
        else res+=max(0,sum[R+n][1]-sum[L+n][1]);
    }
    return res%mod;
}


int main()
{
    cin>>n>>l>>r;
    if( l&1 ) l++;
    if( r&1 ) r--;
    for( int i=1;i<=n;i++ ) cin>>a[i];
    for( int i=1;i<=n;i++ ) a[i]^=a[i-1];
    ll ans=0;
    for( int i=0;i<30;i++ )    ans+=solve(i)*(1<<i)%mod;
    cout<<ans%mod<<endl;
    return 0;
}