补几道异或的题~
链接: here
题解: 求前缀异或和(?)
然后按统计1的个数cnt,显然只有1和配对的区间才能使得最后的值为1, 于是贡献度为 (n - cnt) * cnt + cnt, 再乘上该位的权 1<<pos
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 100010; 4 int a[maxn]; 5 #define LL long long 6 int n; 7 LL ans; 8 void qy(int pos){ 9 LL pre = 0; 10 LL cnt = 0; 11 for(int i = 0; i < n; i++){ 12 pre ^= (a[i] >> pos) & 1; 13 if(pre) cnt++; 14 } 15 ans += cnt * (n + 1 - cnt) * (1LL << pos); 16 } 17 int main(){ 18 while(scanf("%d", &n) != EOF){ 19 ans = 0; 20 for(int i = 0; i < n; i++) scanf("%d", &a[i]); 21 for(int i = 0; i < 30; i++) qy(i); 22 printf("%lld ", ans); 23 } 24 }