BZOJ3687 计算子集和的异或和

时间:2022-05-22 04:55:48

题不知道怎么不见了,bzoj上已经没了3687这题了

题意:给你一个n 然后输入n个数 求这n个数的所有子集的和的异或和

思路:用bitset记录某个数是否在子集和中出现,利用bitset对二进制位的快速大量操作(移位),通过已经求出的子集和求出剩余的子集和

参考代码:

 #include <iostream>
#include <algorithm>
#include <string.h>
#include <map>
#include <bitset>
#include <stdio.h>
#include <vector>
#define ll long long
using namespace std; int main()
{
ll n,x,ans,sum;
while(~scanf("%I64d",&n))
{
bitset<>b;
b[]=;
sum=ans=;
for(ll i=; i<n; i++)
{
scanf("%I64d",&x);
b^=b<<x;
sum+=x;
}
for(ll i=; i<=sum; i++)
{
if(b[i]) ans^=i;
}
printf("%I64d\n",ans);
}
return ;
}