题意:给定一个大小为(n)的可重集合,求其所有子集的算术和的异或和.(n<=1000,sum a_i<=2000000.)
分析:开一个长度为(2000000)的(bitset),第(i)位表示是否有子集的算术和为(i).考虑如何维护这个(bitset),假设现在加入一个数(x)到集合中,那么新得到的算术和 为 原先所有能够得到的算术和(+x)(初始化(0)是能够得到的),即(f<<x),然后加上原先本来能够得到的是(f),因为要考虑这是个可重集合,两个相同的数异或起来就没了,所以是(f)^(=f<<x).如果实在不懂的话,手玩几个简单的例子吧.
快读超时(???)用(scanf)就过了.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#define ll long long
using namespace std;
bitset<2000100>f;
int main(){
int n,sum=0,ans=0;
scanf("%d",&n);f[0]=1;
for(int i=1;i<=n;++i){
int x;scanf("%d",&x);
f^=f<<x;
sum+=x;
}
for(int i=1;i<=sum;++i)if(f[i])ans^=i;
printf("%d
",ans);
return 0;
}