传送门
题意：给定序列求所有区间异或和的和。
思路：经典异或题，显然需要按照位来计算贡献。我们需要先预处理前缀异或和，这样便于计算区间。对于当前位 i i i，我们只需看这个区间的异或和的该位是否为1，也就是该区间该位为1的个数为奇数，记 c n t [ j ] cnt[j] cnt[j]为前 j j j个数异或和位为 1 1 1的个数，显然对于区间 [ l , r ] [l,r] [l,r]我们只需让 c n t [ r ] ⊕ c n t [ l − 1 ] cnt[r]\oplus cnt[l-1] cnt[r]⊕cnt[l−1]为奇数，即 c n t [ l − 1 ] , c n t [ r ] cnt[l-1],cnt[r] cnt[l−1],cnt[r]奇偶性不同即可。
所以统计前缀和有多少个1，每个1都可以与剩下的0组成区间，对于 [ 0 , r ] [0,r] [0,r]，显然0的个数是 r + 1 − c n t [ r ] r+1-cnt[r] r+1−cnt[r]。利用乘法原理再乘上 2 i 2^i 2i 即是该位的贡献。
时间复杂度： O ( 32 n ) O(32n) O(32n)
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+5,M=1e6+5,inf=0x3f3f3f3f,mod=1e9+7; #define mst(a) memset(a,0,sizeof a) #define lx x<<1 #define rx x<<1|1 #define reg register #define PII pair<int,int> #define fi first #define se second int a[N],n; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]^=a[i-1]; ll ans=0; for(int i=0,x=(1<<i);i<32;i++,x<<=1){ int cnt=0; for(int j=1;j<=n;j++) if((a[j]>>i)&1) cnt++; ans+=1LL*cnt*(n+1-cnt)*x; } printf("%lld\n",ans); return 0; }思路2：不用预处前缀异或和，直接计算区间为奇数的个数，类似 d p dp dp的思想，
如果 a [ i ] a[i] a[i]的第 j j j位为1，进行交换 0 , 1 0,1 0,1片段， s u m = i − s u m sum=i-sum sum=i−sum, 因为之前的以 第 i − 1 个 数 的 结 尾 的 区 间 个 数 为 s u m 第i-1个数的结尾的区间个数为sum 第i−1个数的结尾的区间个数为sum，再加上该位的 1 1 1,区间1变成偶数个，所以应该取区间为 0 0 0的部分作为贡献。 时间复杂度: O ( 32 n ) O(32n) O(32n)
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+5,M=1e6+5,inf=0x3f3f3f3f,mod=1e9+7; #define mst(a) memset(a,0,sizeof a) #define lx x<<1 #define rx x<<1|1 #define reg register #define PII pair<int,int> #define fi first #define se second int a[N],n; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); ll ans=0; for(int i=0,x=(1<<i);i<32;i++,x<<=1){ ll sum=0,cnt=0; for(int j=1;j<=n;j++){ if((a[j]>>i)&1) sum=j-sum; cnt+=sum; } ans+=cnt*x; } printf("%lld\n",ans); return 0; }