Loading... 背包+bitset <!--more--> $n$个数所有子集的和的异或$(n \leq 1000)$ 枚举所有子集进行求解复杂度为$2^n$，这是肯定不行的. 背包可以求出任意集合所能组成的数，也就是能够得到该集合的任意子集所组成的数，但是仅仅知道能否组成一个数，无法知道所有的子集中组成了几个这样的数，也无法知道是由哪个子集组成的，当然本题不需要知道是谁组成的，我们只关心组成的数是多少(即和是多少)，并且出现的次数的奇偶性。 我们用bitset优化这个背包，这次其第$i$位不再表示$i$是否能由这个集合的若干个数的和组成，而是表示i出现的次数的奇偶性，既是这个集合所有子集组成奇偶次i,最后统计答案即可. 往背包中加入一个数$x$，新加入的部分为 $f<<x$,而原来的部分仍然是 $f$ , f是原集合的一个子集，$f<<x$也是 ， 直接异或即可。复杂度$O(n*2e6/32)$ ```cpp #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; } ``` Last modification：February 5th, 2020 at 09:06 pm © 允许规范转载 Support 如果觉得我的文章对你有用，请随意赞赏 ×Close Appreciate the author Sweeping payments Pay by AliPay Pay by WeChat
