题目大意：给定一个长度为 $n$ 的序列 $a$，求所有子集和的异或和。$n \leq 1000, \sum a_i \leq 2 \times 10^6$
直接背包是 $O(n\sum a_i)$ 的，设 $f[i][j]$ 表示到第 $i$ 个数，$j$ 这个和出现了奇/偶数次，转移方程如下（当然可以省略第一维）
发现 $f$ 数组只有 $0,1$ 两个值，非常浪费，考虑用 $bitset$ 优化。
令 $bitset$ 的第 $i$ 位表示 $i$ 这个和出现了奇/偶次，设当前数字为 $x$，让 $bitset$ 异或一下右移 $x$ 位的状态即可。
#include <cstdio>
#include <bitset>
const int N = 2000005;
std::bitset<N> b; int n, x;
int main() {
scanf("%d", &n);
b[0] = 1;
for (int i = 1; i <= n; ++i) {
scanf("%d", &x);
b ^= (b << x);
}
x = 0;
for (int i = 1; i <= N; ++i)
if (b[i]) x ^= i;
printf("%d\n", x);
return 0;
}
时间复杂度 $O(\sum a_i)$