BZOJ 3687
Retired_Doubeecat
2021-05-18 16:51:13
> [BZOJ3687](https://www.luogu.com.cn/problem/U162587)
>
> 给定一个可重集，求子集的算数和的异或和。
>
> $1 \leq n \leq 1000,\sum a_i \leq 2 \times 10 ^ 6$
<!-- more -->
## 解题思路：
首先这个问题如果没有 $\sum a_i \leq 2 \times 10 ^ 6$ 是一个经典背包，代码大概是
```cpp
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 的本质，这个循环中
```cpp
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
```cpp
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;
}
```