[BZOJ3687] 简单题

bitset的操作。

因为bitset左右移很快，然后每加进来一个数相当与给所有的子集都加这个数。因为我们只关心每个数出现次数的奇偶性，然后就相当与f[i]^=f[i-x]。然后就发现对于每个数，可以让原有的xor下自身左移x位，用bitset优化即可。

#include <iostream>
#include <cstdio>
#include <bitset>
using namespace std;
const int N=2000005;
bitset<N> b;
int n,f[N];
int main() {
    scanf("%d",&n);
    b[0]=1;
    for(int i=1,x;i<=n;i++) {
        scanf("%d",&x);
        b=(b^(b<<x));
    }
    int ans=0;
    for(int i=1;i<N;i++) if(b[i]) ans^=i;
    cout<<ans<<endl;
    return 0;
}