[bzoj3687]簡單題 bitset

3687: 簡單題

Time Limit: 10 Sec   Memory Limit: 512 MB

[ Submit][ Status][ Discuss]

Description

小呆開始研究集合論了，他提出了關于一個數集四個問題：

1．子集的異或和的算術和。

2．子集的異或和的異或和。

3．子集的算術和的算術和。

4．子集的算術和的異或和。

    目前為止，小呆已經解決了前三個問題，還剩下最後一個問題還沒有解決，他決定把

這個問題交給你，未來的集訓隊隊員來實作。

Input

第一行，一個整數n。

第二行，n個正整數，表示01，a2…．，。

Output

 一行，包含一個整數，表示所有子集和的異或和。

Sample Input

2

1 3

Sample Output

6

HINT

【樣例解釋】

  6=1 異或 3 異或 (1+3)

【資料規模與約定】

ai >0，1<n<1000，∑ai≤2000000。

另外，不保證集合中的數滿足互異性，即有可能出現Ai= Aj且i不等于J

Source

我A這道題的時候還是Too Young Too Simple，什麼都不識得，就上了第一頁 其實bitset就是一個bool數組，但是可以整體進行位運算操作的東西 這道題裡面就是存的是一個值會不會被加到，然後可以知道偶數個1相當于0，奇數個1相當于1 然後一個數x的話，不會影響比x小的值（有點亂）

#include<iostream>
#include<cstring>
#include<bitset>
#include<cstdio>
using namespace std;
int n,x,sum,ans;
bitset<2000000> a;
int main(){
	scanf("%d",&n); a[0]=1;
	while(n--){
		scanf("%d",&x);
		sum += x; a ^= (a<<x);
	}
	for( int i = 1; i <= sum; i++ ) if(a[i]) ans ^= i;
	printf("%d", ans);
	return 0;
}