solution
先对求一遍前缀异或和。
首先肯定要按二进制位处理,假设处理到了第x位,然后枚举一个位置,我们就想要查询所有满足且为偶数的中满足,其中表示第i个位置的第个二进制位上的值。
所以我们只要根据奇偶性分一下类,然后做前缀和就可以求出所有满足条件的的个数了。
code
/* * @Author: wxyww * @Date: 2020-05-22 14:14:55 * @Last Modified time: 2020-05-22 15:11:52 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<ctime> #include<cmath> using namespace std; typedef long long ll; const int N = 200010,mod = 1e9 + 7; ll read() { ll x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f; } int a[N],sum[N][2],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 ans = 0; // if(!x) printf("%d %d\n",sum[0 + n][0],sum[3 + n][0]); for(int i = 1;i <= n;++i) { int r = i - L,l = i - R - 2; // if(x == 0) printf("%d %d ",l,r); if(a[i] >> x & 1) { ans += max(0,sum[r + n][0] - sum[l + n][0]); // if(!x) printf("%d\n",max(0,sum[r + n][0] - sum[l + n][0])); } else { ans += max(0,sum[r + n][1] - sum[l + n][1]); // if(!x) printf("%d\n",max(0,sum[r + n][1] - sum[l + n][1])); } } // printf("%d %lld\n",x,ans); return ans % mod; } int main() { n = read(),L = read(),R = read(); if(L & 1) ++L;if(R & 1) --R; for(int i = 1;i <= n;++i) a[i] = read() ^ a[i - 1]; // for(int i = 1;i <= n;++i) printf("%d ",a[i]); ll ans = 0; for(int i = 0;i < 31;++i) ans += solve(i) * (1 << i) % mod; cout<<ans % mod<<endl; return 0; }