P3917 异或序列

时间:2021-03-15 20:27:47

P3917 异或序列
暴力前缀异或枚举每一个区间,再求和,60分。
正解:
按每一位来做
对于区间[l,r],如果它对答案有贡献,区间中1的个数一定是奇数,可以按每一位取(1<<i)的前缀和,q[r]-q[l-1]一定是奇数,那只要保证端点值奇偶性不同即可。根据乘法原理,奇数*偶数就是满足条件的区间个数,这个是前缀和。
也可以用前缀异或,道理一样。

 #include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<cstring>
#define inf 2147483647
#define For(i,a,b) for(register long long i=a;i<=b;i++)
#define p(a) putchar(a)
#define g() getchar()
//by war
//2017.10.23
using namespace std;
long long n;
long long a[];
long long cnt;
long long ans;
void in(long long &x)
{
long long y=;
char c=g();x=;
while(c<''||c>'')
{
if(c=='-')
y=-;
c=g();
}
while(c<=''&&c>='')x=x*+c-'',c=g();
x*=y;
}
void o(long long x)
{
if(x<)
{
p('-');
x=-x;
}
if(x>)o(x/);
p(x%+'');
}
int main()
{
in(n);
For(i,,n)
{
in(a[i]);
a[i]^=a[i-];
}
For(i,,)
{
cnt=;
For(j,,n)
if((a[j]>>i)&==)
cnt++;
ans+=cnt*(n-cnt+)*(<<i);
}
o(ans);
return ;
}