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

一.题目链接：

$\quad$ 小AA的数列

二.题目大意：

$\quad$ 给 n 个数，求区间长度为偶数，且区间长度在 [L, R] 的区间异或和的加和.

三.分析

$\quad$ 众所周知，异或题的一种经典解法就是按照分别按照位权计算贡献.

$\quad$ 假设当前枚举到二进制位 i，那么当前二进制位 i 对答案的贡献就是 2^i * 异或和第 i 位为 1 的区间个数.

$\quad$ 那么问题转化为求解异或和第 i 位为 1 的区间个数.

$\quad$ 记 c[i, j] 表示第偶/奇(i=0/1)个数，前缀异或和为 j 的方案数.

四.代码实现

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

typedef long long ll;

const int M = (int)1e5;
const ll mod = (ll)1e9 + 7;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;

int a[M + 5];

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    int n, l, r; scanf("%d %d %d", &n, &l, &r);
    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]), a[i] ^= a[i - 1];
    if(l & 1) ++l; if(r & 1) --r;
    if(l > r) {printf("0\n"); return 0;}
    ll ans = 0;
    for(int i = 0; i < 31; ++i)
    {
        int c[2][2] = {0};
        for(int j = 1; j <= n; ++j)
        {
            if(l <= j) ++c[j & 1][(a[j - l]>>i) & 1];
            ans = (ans + (1ll<<i) * c[j & 1][((a[j]>>i) & 1) ^ 1]) % mod;
            if(r <= j) --c[j & 1][(a[j - r]>>i) & 1];
        }
    }
    printf("%lld\n", ans);
    return 0;
}