題目傳送門
前幾天的考試考到了bitset，于是我就去學了一發。
大佬傳送門，這位大佬已經講的很清楚了，我就不再贅述bitset的功能和用法了。
其實說白了，bitset就是一個可以位運算的bool數組罷了。
回到這題，我們可以很容易想到的是DP，定義f[i[表示目前子集的算術和為i的子集構成方案數。
狀态轉移方程也非常好想，f[j]+=f[j-a[i]]
然後就是統計答案，若f[i]&1>0，則ans^=i。
這題真的這麼簡單嗎？難道出題人變得有良心了？孩子，别做夢了。
觀察上面的狀态轉移方程和答案統計，我們可以發現最後的答案統計隻和f[i]的奇偶性有關，于是我們可以把轉移方程變成f[j]^=f[j-a[i]]
然後，根據異或的性質，我們又可以把方程轉化成f[j]^=f[j-a[i]]<<a[i] -> ans^=ans<<a[i]（至于為什麼，我也不知道……）
然後問題就變得很簡單了，隻要O(n)掃一遍，邊讀入邊統計答案，最後統計答案時再掃一遍就好了。
附上AC代碼：
#include <cstdio>
#include <bitset>
using namespace std;
bitset <2000010> a;
int n,x,sum,ans;
int main(void){
scanf("%d",&n),a.set(0);
for (int i=1; i<=n; ++i) 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;
}