Description

小呆开始研究集合论了，他提出了关于一个数集四个问题：
1. 子集的异或和的算术和。
2. 子集的异或和的异或和。
3. 子集的算术和的算术和。
4. 子集的算术和的异或和。
目前为止，小呆已经解决了前三个问题，还剩下最后一个问题还没有解决，他决定把
这个问题交给你，未来的集训队队员来实现。

Input

第一行，一个整数 n。
第二行，n 个正整数，表示 a1, a2, …, an
ai > 0，1 ≤ n ≤ 1000，
∑ ai ≤ 2000000。
另外，不保证集合中的数满足互异性，即有可能出现 ai = aj 且 i != j。

Output

一行，包含一个整数，表示所有子集和的异或和。

Sample Input

2
1 3

Sample Output

6
【样例解释】
6 = 1 ⊗ 3 ⊗ (1 + 3)

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 bitset<2000001>b;
 4 int main() {
 5     b[0]=1;
 6     int n,a[2000001],ans=0,sum=0;
 7     cin>>n;
 8     for(int i=1; i<=n; i++)
 9         cin>>a[i],sum+=a[i];
10     for(int i=1; i<=n; i++)
11         b=b^(b<<a[i]);
12     for(int i=1; i<=sum; i++)
13         if(b[i])
14             ans^=i;
15     printf("%d",ans);
16     return 0;
17 }

View Code