Doubeecat's Blog

“即便前路混沌,同她走过,才算人间。”

0%

BZOJ 3687 简单题 解题报告

BZOJ3687

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

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

解题思路:

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

1
2
3
4
5
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 的本质,这个循环中

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

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

1
2
3
4
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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;
}