给出n个数,求所有子集和的异或和。n<=2e6.
正常情况下就是一个01背包,但是范围过大会TLE
于是用bitset优化一下这个bool dp
bitset的第i位表示和为i出现次数的奇偶性
这个东西可以像位运算一样操作,比较方便但是好像用的不多。。
#include<bits/stdc++.h>
#define LL long long
#define clr(x,i) memset(x,i,sizeof(x))
using namespace std;
const int N=2000005;
bitset<N> a;
int n;
int main()
{
scanf("%d",&n);
int x,sum=0,ans=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
a^=(a<<x);a[x]?a[x]=0:a[x]=1;sum+=x;
//for(int i=0;i<=sum;i++)printf("%d ",a[i]?1:0);puts("");
}
for(int i=1;i<=sum;i++)
if(a[i])ans^=i;
printf("%d",ans);
return 0;
}