题目描述

给出序列A1,A2,⋯,ANA_1,A_2,\cdots,A_NA1​,A2​,⋯,AN​，求

∑1≤i≤j≤NAi⨁Ai+1⨁⋯⨁Aj\sum_{1\le i\le j\le N} A_i\bigoplus A_{i+1}\bigoplus\cdots\bigoplus A_j∑1≤i≤j≤N​Ai​⨁Ai+1​⨁⋯⨁Aj​

的值。其中，⨁\bigoplus⨁表示按位异或。

输入输出格式

输入格式：

第1 行，1 个整数NNN。

第2 行，NNN个整数A1,A2,⋯,ANA_1,A_2,\cdots,A_NA1​,A2​,⋯,AN​。

输出格式：

一个数，为表达式的值

输入输出样例

输入样例#1：

21 2

输出样例#1：

6

说明

• 对于60% 的数据，1≤N≤1031 \le N \le 10^31≤N≤103；

• 对于100% 的数据，1≤N≤105;0≤Ai≤1091 \le N \le 10^5; 0 \le A_i \le 10^91≤N≤105;0≤Ai​≤109。

思路

对于二进制的每位，n个数取前缀和；

对于区间(l,r)，如果q[l-1]+q[r]=奇数，说明该区间异或和有该位；

N个前缀和中奇数与偶数之积即为含有该位的区间的个数；

代码

1 #include
      
        2 #define LL long long 3 const int maxn=1e5+10; 4 LL n,ans; 5 LL s[maxn]; 6 LL q[16][maxn]; 7 int main(){ 8     scanf("%lld",&n); 9     for(int i=1;i<=n;i++) scanf("%d",&s[i]);10     LL a,b;11     for(LL i=0,j=1;i<16;i++,j<<=1){12         a=0,b=1;13         for(LL k=1;k<=n;k++){14             if(s[k]&j) q[i][k]++;15             q[i][k]+=q[i][k-1];16             if(q[i][k]&1) a++;17             else b++;18         }19         ans+=a*b*j;20     }21     printf("%lld",ans);22     return 0;23 }