P3917 異或序列(位運算）

P3917 異或序列(位運算）

傳送門

題意：給定序列求所有區間異或和的和。

思路：經典異或題，顯然需要按照位來計算貢獻。我們需要先預處理字首異或和，這樣便于計算區間。對于目前位

i

i

i，我們隻需看這個區間的異或和的該位是否為1，也就是該區間該位為1的個數為奇數，記

c

n

t

[

j

]

cnt[j]

cnt[j]為前

j

j個數異或和位為

1

1的個數，顯然對于區間

l

,

r

[l,r]

[l,r]我們隻需讓

⊕

−

cnt[r]\oplus cnt[l-1]

cnt[r]⊕cnt[l−1]為奇數，即

cnt[l-1],cnt[r]

cnt[l−1],cnt[r]奇偶性不同即可。

是以統計字首和有多少個1，每個1都可以與剩下的0組成區間，對于

[0,r]

[0,r]，顯然0的個數是

+

r+1-cnt[r]

r+1−cnt[r]。利用乘法原理再乘上

2

i

2^i

2i 即是該位的貢獻。

時間複雜度：

O

(

32

)

O(32n)

O(32n)

#include<bits/stdc++.h>     using namespace std;     typedef long long ll;     const int N=1e5+5,M=1e6+5,inf=0x3f3f3f3f,mod=1e9+7;     #define mst(a) memset(a,0,sizeof a)     #define lx x<<1     #define rx x<<1|1     #define reg register     #define PII pair<int,int>     #define fi first      #define se second     int a[N],n;     int main(){     	scanf("%d",&n);     	for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]^=a[i-1];     	ll ans=0;     	for(int i=0,x=(1<<i);i<32;i++,x<<=1){     		int cnt=0;     		  for(int j=1;j<=n;j++)     		  	  if((a[j]>>i)&1) cnt++;     		  ans+=1LL*cnt*(n+1-cnt)*x;     	}     	printf("%lld\n",ans);     	return 0;     }           

思路2：不用預處字首異或和，直接計算區間為奇數的個數，類似

d

p

dp

dp的思想，

如果

a

a[i]

a[i]的第

j位為1，進行交換

0,1

0,1片段，

s

u

m

=

sum=i-sum

sum=i−sum, 因為之前的以

第

個

數

的

結

尾

區

間

為

第i-1個數的結尾的區間個數為sum

第i−1個數的結尾的區間個數為sum，再加上該位的

1,區間1變成偶數個，是以應該取區間為

0的部分作為貢獻。 時間複雜度:

#include<bits/stdc++.h>     using namespace std;     typedef long long ll;     const int N=1e5+5,M=1e6+5,inf=0x3f3f3f3f,mod=1e9+7;     #define mst(a) memset(a,0,sizeof a)     #define lx x<<1     #define rx x<<1|1     #define reg register     #define PII pair<int,int>     #define fi first      #define se second     int a[N],n;     int main(){     	scanf("%d",&n);     	for(int i=1;i<=n;i++) scanf("%d",&a[i]);     	ll ans=0;     	for(int i=0,x=(1<<i);i<32;i++,x<<=1){     		ll sum=0,cnt=0;     		  for(int j=1;j<=n;j++){     		  	  if((a[j]>>i)&1) sum=j-sum;     		  	cnt+=sum;     		   }     		  ans+=cnt*x;     	}     	printf("%lld\n",ans);     	return 0;     }