马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？立即注册
x
abc365 E-Xor Sigma Problem
思路
本题首先可以想到用前缀异或和维护，我们记作 b i = a 1 ⊕ a 2 ⊕ ⋅ ⋅ ⋅ ⊕ a i b_i=a_1\oplus a_2 \oplus ··· \oplus a_i bi=a1⊕a2⊕⋅⋅⋅⊕ai，所求的式子就酿成了 ∑ i = 0 n − 2 ∑ j = i + 2 n b i ⊕ b j \sum^{n-2}_{i=0}\sum^n_{j=i+2}b_i\oplus b_j ∑i=0n−2∑j=i+2nbi⊕bj，直接求是 O ( n 2 ) O(n^2) O(n2)的，考虑怎样快速求出 ∑ i = 0 x − 1 b i ⊕ b x \sum^{x-1}_{i=0}b_i\oplus b_x ∑i=0x−1bi⊕bx
因为这是位运算，以是我们不难想到按位考虑，我们记 g i , j g_{i,j} gi,j为当前考虑范围内第 q q q位为 p ( 0 , 1 ) p(0,1) p(0,1)的个数，我们动态维护 b 1... i b1...i b1...i总的 g q , p g_{q,p} gq,p，当我们枚举到第 b i + 1 b_{i+1} bi+1时，如果此时的第 j j j位为 1 1 1，那么 g i , 0 g_{i,0} gi,0将是有贡献的，反之同理
代码
来自Andy1262
- #include<bits/stdc++.h>
- using namespace std;
- inline long long read(){
- long long ans=0,f=1;
- char c=getchar();
- while(c<'0'||c>'9'){
- if(c=='-') f=-f;
- c=getchar();
- }
- while(c>='0'&&c<='9'){
- ans=(ans<<3)+(ans<<1)+c-48;
- c=getchar();
- }
- return ans*f;
- }
- void write(long long x){
- if(x<0){
- putchar('-');
- x=-x;
- }
- if(x<10) putchar(x+48);
- else{
- write(x/10);
- putchar(x%10+48);
- }
- }
- long long n;
- long long a[200005],b[200005];
- long long g[35][2];
- long long ans;
- signed main(){
- n=read();
- for(long long i=1;i<=n;i++){
- a[i]=read();
- b[i]=a[i]^b[i-1];
- }
- for(long long i=0;i<=28;i++) g[i][0]++;//将b[0]加进去
- for(long long i=1;i<=n;i++){
- for(long long j=0;j<=28;j++){
- ans+=g[j][bool((b[i])&(1<<j))^1]*(1<<j);//按位统计答案
- }
- for(long long j=0;j<=28;j++){
- g[j][bool((b[i])&(1<<j))]++;//按位更新g数组
- }
- }
- for(long long i=1;i<=n;i++) ans-=a[i];//除去长度为1的区间
- write(ans);
- return 0;
- }
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
