BZOJ3687 简单题 dp+bitset

简单题 dp+bitset"/>

BZOJ3687 简单题 dp+bitset

给出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;
}