题解 | #小AA的数列#

链接：小AA的数列

题意：求长度在 区间内的偶数长度区间异或和之和。

题解：显然区间异或和的和可以按为拆开分开计算，最后在累加上去（因为每一位异或时互不干扰）。现在考虑怎么把范围限制在 中。可以发现，我们容易求出大于某个数的长度的答案，所以答案就是 (数位 计算区间答案的思想)。递推时注意 是可由 的答案继承过来的，但是在算答案累加时是得按最短长度去继承的。

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const int mod=1e9+7;

ll f[maxn][2],s[maxn],a[maxn],n,L,R;

inline void update(int j)
{
    int p=s[j]^s[j-2];
    if(p)
    {
        f[j][0]=f[j-2][1];
        f[j][1]=f[j-2][0]+1;
    }
    else
    { 
        f[j][0]=f[j-2][0]+1;
        f[j][1]=f[j-2][1];
    }
}

inline ll DP(int len)
{
    ll ans=0;
    for(int i=0;i<=31;i++)
    {
        ll tmp=0; f[0][0]=f[0][1]=f[1][0]=f[1][1]=0;
        for(int j=1;j<len;j++)
        {
            s[j]=s[j-1]^((1ll<<i)&a[j]);
        }
        for(int j=2;j<len;j++)update(j);
        for(int j=len;j<=n;j++)
        {
            s[j]=s[j-1]^((1ll<<i)&a[j]);
            int p=s[j]^s[j-len];
            if(p)tmp+=f[j-len][0]+1;
            else tmp+=f[j-len][1];
            update(j);
        }
        ans=(ans+(1ll<<i)*tmp%mod)%mod;
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>n>>L>>R;
    int l1=(L+1>>1)<<1,l2=(R>>1)+1<<1; 
    for(int i=1;i<=n;i++)cin>>a[i];
    cout<<((DP(l1)-DP(l2))%mod+mod)%mod<<endl;
    return 0; 
}