题目描述

给出有 $n$ 个数 $a_i$ 的可重集合，求其子集的算术和的异或和。

输入格式

第一行一个整数 $n \ (1 \le n \le 1000)$。

第二行 $n$ 个正整数 $a_i \ ( a_i >0, \sum a_i \le 2 \times 10^6)$ 。

输出格式

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

样例输入

2
1 3

样例输出

6

样例解释

$6 = 1 \ \ \ XOR \ \ \ 3 \ \ \ XOR \ \ \ (1+3)$

介绍

std::bitset 是标准库中的一个存储 0/1 的大小不可变容器。严格来讲，它并不属于 STL。

由于内存地址是按字节即 byte 寻址，而非比特 bit，一个 bool 类型的变量，虽然只能表示 0/1, 但是也占了 1 byte 的内存。

bitset 就是通过固定的优化，使得一个字节的八个比特能分别储存 8 位的 0/1。

对于一个 4 字节的 int 变量，在只存 0/1 的意义下，bitset 占用空间只是其 $\frac{1}{32}$，计算一些信息时，所需时间也是其 $\frac 1{32}$。

在某些情况下通过 bitset 可以优化程序的运行效率。至于其优化的是复杂度还是常数，要看计算复杂度的角度。一般 bitset 的复杂度有以下几种记法：（设原复杂度为 $O(n)$）

1. $O(n)$，这种记法认为 bitset 完全没有优化复杂度。
2. $O(\frac n{32})$，这种记法不太严谨（复杂度中不应出现常数），但体现了 bitset 能将所需时间优化至 $\frac 1{32}$。
3. $O(\frac n w)$，其中 $w=32$（计算机的位数），这种记法较为普遍接受。
4. $O(\frac n {\log w})$，其中 $w$ 为计算机一个整型变量的大小。

另外，vector 的一个特化 vector<bool> 的储存方式同 bitset 一样，区别在于其支持动态开空间，bitset 则和我们一般的静态数组一样，是在编译时就开好了的。然而，bitset 有一些好用的库函数，不仅方便，而且有时可以实现 SIMD 进而减小常数。另外，vector<bool> 的部分表现和 vector 不一致（如对 std::vector<bool> vec 来说，$\&vec[0] + i$ 不等于 $\&vec[i]$ ）。因此，一般不使用 vector<bool>。

使用

参见 std::bitset - cppreference.com。

头文件

#include 
```

指定大小

std::bitset  bs;  // a bitset with 1000 bits

构造函数

-   `bitset()`: 每一位都是 `False`。
-   `bitset(unsigned long val)`: 设为 `val` 的二进制形式。
-   `bitset(const string & str)`: 设为 $01$ 串 `str`。

运算符

-   `operator []`: 访问其特定的一位。

-   `operator ==`/`operator !=`: 比较两个 `bitset` 内容是否完全一样。

-   `operator &`/`operator &=`/`operator |`/`operator |=`/`operator ^`/`operator ^=`/`operator ~`: 进行按位与/或/异或/取反操作。

    注意：**`bitset` 只能与 `bitset` 进行位运算**，若要和整型进行位运算，要先将整型转换为 `bitset`。

-   `operator <>`/`operator <>=`: 进行二进制左移/右移。

此外，`bitset` 还提供了 C++ 流式 IO 的支持，这意味着你可以通过 `cin/cout` 进行输入输出。

成员函数

-   `count()`: 返回 `True` 的数量。
-   `size()`: 返回 `bitset` 的大小。
-   `test(pos)`: 它和 `vector` 中的 `at()` 的作用是一样的，和 `[]` 运算符的区别就是越界检查。
-   `any()`: 若存在某一位是 `True` 则返回 `True`，否则返回 `False`。
-   `none()`: 若所有位都是 `False` 则返回 `True`，否则返回 `False`。
-   `all()`: 若所有位都是 `True` 则返回 `True`，否则返回 `False`。
-   1.  `set()`: 将整个 `bitset` 设置成 `True`。
    2.  `set(pos, val = True)`: 将某一位设置成 `True`/`False`。
-   1.  `reset()`: 将整个 `bitset` 设置成 `False`。
    2.  `reset(pos)`: 将某一位设置成 `False`。相当于 `set(pos, False)`。
-   1.  `flip()`: 翻转每一位。（$0\leftrightarrow1$，相当于异或一个全是 $1$ 的 `bitset`）
    2.  `flip(pos)`: 翻转某一位。
-   `to_string()`: 返回转换成的字符串表达。
-   `to_ulong()`: 返回转换成的 `unsigned long` 表达（`long` 在 NT 及 32 位 POSIX 系统下与 `int` 一样，在 64 位 POSIX 下与 `long long` 一样）。
-   `to_ullong()`:（**C++11** 起）返回转换成的 `unsigned long long` 表达。

另外，libstdc++ 中有一些较为实用的内部成员函数[^bitset1]：

-   `_Find_first()`: 返回 `bitset` 第一个 `True` 的下标，若没有 `True` 则返回 `bitset` 的大小。
-   `_Find_next(pos)`: 返回 `pos` 后面（下标严格大于 `pos` 的位置）第一个 `True` 的下标，若 `pos` 后面没有 `True` 则返回 `bitset` 的大小。