序列异或求贡献是一类常见的题目，经典做法无非是求前后缀，按进制位拆贡献累计答案，但是需要对具体问题具体分析。
异或和之和
设前缀异或和为 \(sum_i\)（\(sum_0\)=0），对 \(sum_i\) 二进制拆位。\(tot1_k\) 为二进制拆位第 \(k\) 位为 \(1\) 的数的个数，\(tot0_k\) 为二进制拆位第 \(k\) 位为 \(0\) 的数的个数。推式子：
\[\sum_{L=1}^{n}\sum_{R=L}^n\bigoplus_{i=L}^Ra_i
\]
\[=\sum_{L=1}^{n}\sum_{R=L}^nsum_R-sum_{L-1}
\]
\[=\sum_{L=1}^{n}\sum_{R=L}^nsum_R-sum_{L-1}
\]
\[=\sum_{k=0}^{20}tot1_k\times tot0_k\times 2^k
\]
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,ans(0);
int a[N];
signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n;a[0]=0;for(int i=1;i<=n;++i) cin>>a[i],a[i]^=a[i-1];for(int k=0;k<21;++k){int tot[2]={0,0};for(int i=0;i<=n;++i){ans+=tot[!(a[i]>>k&1)]*(1<<k);//边扫边统计和最后算乘积是一样的tot[1]+=a[i]>>k&1;tot[0]+=!(a[i]>>k&1);}}cout<<ans<<endl;return 0;
}
异或平方和
据说是 \(ACM\) 省赛金牌题......真的假的
对 \(a_i\) 二进制拆位：
设 \(tot10_{m,k}\) 为二进制拆位第 \(m\) 位为 \(1\)，\(k\) 位为 \(0\) 的 \(a_i\) 的个数。
设 \(tot01_{m,k}\) 为二进制拆位第 \(m\) 位为 \(0\)，\(k\) 位为 \(1\) 的 \(a_i\) 的个数。
设 \(tot11_{m,k}\) 为二进制拆位第 \(m\) 位为 \(1\)，\(k\) 位为 \(1\) 的 \(a_i\) 的个数。
设 \(tot00_{m,k}\) 为二进制拆位第 \(m\) 位为 \(0\)，\(k\) 位为 \(0\) 的 \(a_i\) 的个数。
设 \(tot0_{m}\) 为二进制拆位第 \(m\) 位为 \(0\) 的 \(a_i\) 的个数。
设 \(tot1_{m}\) 为二进制拆位第 \(m\) 位为 \(1\) 的 \(a_i\) 的个数（实际上这个不就是 \(n-tot0_m\) 嘛）。
推式子：
\[\begin{aligned}
&\sum_{i=1}^{n}\sum_{j=1}^n(a_i\oplus a_j)^2\\=&\left(\sum_{m=0}^{31}\sum_{k=0}^{31}tot01_{m,k}\times tot10_{m,k}\times 2^{k+1}\right)+\\
&\left(\sum_{m=0}^{31}\sum_{k=0}^{31}tot00_{m,k}\times tot11_{m,k}\times 2^{k+1}\right)+\\
&\left(\sum_{m=0}^{31}\times tot1_{m}\times tot0_{m}\times 2^{2k}\right)\\
\end{aligned}
\]
当然你也可以边扫边统计贡献，一样的。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10,p=1e9+7;
int n,ans(0);
int a[N],fac[N];
int c[100],c01[50][50],c10[50][50],c11[50][50],c00[50][50];
signed main(){// freopen("data","r",stdin);// freopen("my.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;++i) cin>>a[i];fac[0]=1;for(int i=1;i<=50;++i) fac[i]=fac[i-1]*2%p;for(int k=0;k<32;++k){for(int i=1;i<=n;++i){c[k]+=a[i]>>k&1;}for(int m=k+1;m<32;++m){for(int i=1;i<=n;++i){c01[k][m]+=!(a[i]>>k&1)&&(a[i]>>m&1);c10[k][m]+=(a[i]>>k&1)&&!(a[i]>>m&1);c11[k][m]+=(a[i]>>k&1)&&(a[i]>>m&1);c00[k][m]+=!(a[i]>>k&1)&&!(a[i]>>m&1);}}}for(int k=0;k<32;++k){for(int m=k+1;m<32;++m){ans=(ans+c01[k][m]*c10[k][m]%p*fac[1+m+k])%p;ans=(ans+c00[k][m]*c11[k][m]%p*fac[1+m+k])%p;}ans=(ans+c[k]*(n-c[k])*fac[k<<1]%p);}cout<<(ans*2)%p<<endl;return 0;
}
异或和
稍微有点不一样，转换一下思路，但是总体肯定还是“前缀和+拆位算贡献”的思想。
\[\bigoplus\sum_{L=1}^{n}\sum_{R=L}^n\sum_{i=L}^Ra_i
\]
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,ans(0),gs(0);
int a[N],fac[N],tem[N];
int num[N][35],res[35];
struct BIT{#define lowbit(x) (x&(-x))int t[N];void add(int pos,int v){if(!pos) t[pos++]+=v;for(int i=pos;i<=N-10;i+=lowbit(i)) t[i]+=v;}int sum(int pos){if(!pos) return t[0];int res(0);for(int i=pos;i;i-=lowbit(i)) res+=t[i];return res;}
}t[35][2];
int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;++i){cin>>a[i];fac[i]=fac[i-1]+a[i];for(int k=0;k<32;++k) num[i][k]=fac[i]&((1<<k+1)-1);}for(int k=0;k<32;++k){for(int i=0;i<=n;++i) tem[i]=num[i][k];sort(tem,tem+n+1);gs=unique(tem,tem+n+1)-tem;for(int i=0;i<=n;++i)num[i][k]=lower_bound(tem,tem+gs,num[i][k])-tem;}for(int k=0;k<32;++k){for(int i=0;i<=n;++i){int f1=t[k][1].sum(num[i][k-1]),f0=t[k][0].sum(num[i][k-1]);int siz1=t[k][1].sum(N-10),siz0=t[k][0].sum(N-10);res[k]+=fac[i]>>k&1?f0+siz1-f1:siz0-f0+f1;t[k][(fac[i]>>k)&1].add(num[i][k-1],1);}}for(int k=0;k<32;++k) ans+=(res[k]&1)*(1<<k);cout<<ans<<endl;
}
Sum of XOR Functions