题意

给定一个含 n n n( n < 1000 n<1000 n<1000)个正整数( Σ a \Sigma{a} Σa ≤ 2 e 6 ≤2e6 ≤2e6)的集合，求其子集和的异或和。

思路

• 枚举子集显然是会超时的，考虑换一种思路。
• 注意到集合内数的总和范围不是很大，所以可以考虑从值域下手，即判断每种可能的和 s s s是否会对答案产生贡献，因为仅当 s s s出现次数为奇数s才会产生贡献，所以只需记录每个 s s s出现的次数。
• 这时，神奇的bitset就派上用场了，用bitset的第 s s s位记录和 s s s是否对答案产生贡献，最后把能产生贡献的和异或即可。

代码

#include<cstdio>
#include<bitset>
using namespace std;
const int maxn=2e6+9;
bitset<maxn>bit;
int read(){
    int x=0;char c=getchar();
    while(c>'9'||c<'0') c=getchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return x;
}
int main(){
    int n=read();
    bit[0]=1;//子集为空集时和为0
    while(n--){
        int x=read();
        bit^=bit<<x;//左移 使得x与之前的所有数都相加了一次
        			//异或 更新了能产生贡献的和
    }
    int ans=0;
    for(int i=2e6;i>=0;i--)
        if(bit[i]==1) ans^=i;//把能产生贡献的异或求和
    printf("%d",ans);
    return 0;
}