简单题

Time Limit: 10 Sec Memory Limit: 512 MB

Description

小呆开始研究集合论了，他提出了关于一个数集四个问题：

1．子集的异或和的算术和。

2．子集的异或和的异或和。

3．子集的算术和的算术和。

4．子集的算术和的异或和。

目前为止，小呆已经解决了前三个问题，还剩下最后一个问题还没有解决，他决定把

这个问题交给你，未来的集训队队员来实现。

Input

第一行，一个整数n。

第二行，n个正整数，表示01，a2…．，。

Output

一行，包含一个整数，表示所有子集和的异或和。

Sample Input

2

1 3

Sample Output

6

HINT

【样例解释】

6=1 异或 3 异或 (1+3)

【数据规模与约定】

ai >0，1<n<1000，∑ai≤2000000。

另外，不保证集合中的数满足互异性，即有可能出现Ai= Aj且i不等于J

这道题首先有的做法就是\(O(n * \sum a_i)\)，特别善良的背包问题。

然而过不了。。。

所以我们来优化一下（这是为什么要写这篇博客）

我们来介绍一下一种清奇的优化方式 \(bitset\) 优化。

这种优化是真的强啊，复杂度直接除以32.。。。（这道题就直接过了啊~）

具体是怎么回事呢？我们来看一下常规思路。。。

设 \(dp[i]\) 表示能凑出和为 \(i\) 的个数。那么状态转移方程显然就是 \(dp[i] += dp[i - k]\) 假设当前的数为k。

那么我们又转念一想，由于异或的特殊性质，自己异或自己为\(0\), \(0\)异或任何一个数等于这个数本身。那么，\(dp[i]\) 也就只有奇数与偶数的区别了啊。。。。

进一步就变成了 \(dp[i] = (dp[i] + dp[i - k]) % 2\)

而\(bitset\)这个东西就开始发挥作用了啊，我现在初步认为这个东西就是一个用起来感觉起飞的\(bool\)数组，由于只有奇偶的差别，也就是说只有两面性（真假）。那么我们就可以用\(bool\)来表达这两个状态了啊。

接下来就是\(bitset\)的展示环节，代码中可以看到，这个玩意儿可以直接左右移！！速度贼快。刚好这道题有一种错位相加的感觉（自己YY一下就好了~）

好了，你也可以开始起飞了。。。

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