BZOJ3687

给定一个可重集，求子集的算数和的异或和。

1 \leq n \leq 1000,\sum a_i \leq 2 \times 10 ^ 6

解题思路：

首先这个问题如果没有 \sum a_i \leq 2 \times 10 ^ 6 是一个经典背包，代码大概是

f[0] = 1;
for (int i = 1;i <= n;++i) {
    for (int j = sum;j >= a[i];--j) {
        f[j] ^= f[j - a[i]];
    }
}

注意这里一个数出现偶数次的话根据异或的性质就等于 0 了，因此我们这里不用保存次数，直接异或即可。

时间复杂度 O(n\sum a_i)

思考一下这个 DP 的本质，这个循环中

for (int j = sum;j >= a[i];--j) {
    f[j] ^= f[j - a[i]];
}

我们的滚动数组实际上干的是这么一回事

a[i] = 2
Flas 0 0 1 0 1 0
Fxor 1 0 1 0 0 0 
Fnow 1 0 0 0 1 0

实际上，可以视为整个数组往左移了两位，那么再注意到我们实际上用到只有 01 两个数，这启发我们使用 bitset 优化！

所以，时间复杂度就变成了 O(\frac{n\sum a_i}{32}) 可以通过。

Code

const int N = 1e3 + 10;
const int M = 2e6 + 10;
bitset <M> f;
int n,a[N],sum,ans;

signed main() {
    cin >> n;
    f[0] = 1;
    for (int i = 1;i <= n;++i) {
        int x;cin >> x;sum += x;
        f = f ^(f<<x);
    }
    for (int i = 1;i <= sum;++i) {
        if (f[i]) ans ^= i;
    }
    printf("%d\n",ans);
    return 0;
}