sequence
给定一个序列，求其所有区间 按位异或的值 的和
题解
按位考虑。。。
比如说对于每个a[i]的第K位
对于一个x，假设得到了i到x-1(i<x)这些区间的异或值。。。即有f0[x-1]个0,f1[x-1]个1，每个1
对答案的贡献是1<<(K-1)
那么对于i到x，仅仅是对于所有区间加入了a[x]这个元素
以及多了仅含a[x]的区间。。
所以若a[x]=1的话，f0[x]=f1[x-1]，f1[x]=f0[x-1]+1
否则f0[x]=f0[x-1]+1,f1[x]=f1[x-1]
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<queue> #include<cmath> #include<vector> #include<algorithm> #include<map> #define ll long long #define inf 2147483647 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n; int a[100005],bin[35]; ll ans; void solve(int x) { int c0=0,c1=0; for(int i=1;i<=n;i++) { if(a[i]&bin[x])swap(c0,c1),c1++; else c0++; ans+=(ll)bin[x]*c1; } } int main() { bin[0]=1;for(int i=1;i<=30;i++)bin[i]=bin[i-1]<<1; n=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=0;i<=30;i++) solve(i); printf("%lld\n",ans); return 0; } |
计数器 9863651
OI 课件=>
OI 课件=>
Orz……