背包+bitset

$n$个数所有子集的和的异或$(n \leq 1000)$
枚举所有子集进行求解复杂度为$2^n$，这是肯定不行的.
背包可以求出任意集合所能组成的数，也就是能够得到该集合的任意子集所组成的数，但是仅仅知道能否组成一个数，无法知道所有的子集中组成了几个这样的数，也无法知道是由哪个子集组成的，当然本题不需要知道是谁组成的，我们只关心组成的数是多少(即和是多少)，并且出现的次数的奇偶性。
我们用bitset优化这个背包，这次其第$i$位不再表示$i$是否能由这个集合的若干个数的和组成，而是表示i出现的次数的奇偶性，既是这个集合所有子集组成奇偶次i,最后统计答案即可.
往背包中加入一个数$x$，新加入的部分为 $f<<x$,而原来的部分仍然是 $f$ , f是原集合的一个子集，$f<<x$也是 ， 直接异或即可。复杂度$O(n*2e6/32)$

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
int n;
bitset < N > f;
 
int main () {
    int x;
    f.set ( 0 );
    scanf ( "%d" , &n );
    for ( int i = 0 ; i < n ; ++ i ) {
        scanf ( "%d" , &x );
        f ^= f << x;
    }
    int ans = 0;
    for ( int i = 0 ; i <= N - 10 ; ++ i ) if ( f[i] ) ans ^= i;
    printf ( "%d\n" , ans );
    return 0;
}