[bzoj 3687]简单题 bitset的运用

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题意

给定一个正整数集，求所有子集算术和的异或和

题解

每次加入一个元素x,用原集合a xor (a<< x) 然后每一个值统计一下

bitset看起来很优越，是一个能位运算的布尔数组

#include<bitset>

#include<stdio.h>

int n,sum,ans;

using namespace std;

bitset<2000000>a;

int main(){

    scanf("%d",&n);

    a[0]=1;

    for(int i=1;i<=n;i++){

        int x;scanf("%d",&x);

        a=a^(a<<x);

    }

    for(int i=1;i<=2000000;i++)if(a[i])ans^=i;

    printf("%d",ans);

}