BZOJ 3687 简单题

发表于 | 分类于

Description

给定一个\(n\)个元素的可重集，求其中所有子集的元素算数和异或起来的结果。

\(n\leq 1000\)，保证集合中元素是正整数，且所有数的和不超过\(2\times 10^6\)。

Solution

被……安排上了

所有可能的自己算术和只有\(2\times 10^6\)种（不考虑\(0\)），每种会不会在答案中出现只取决于这一类和出现的子集是奇数个还是偶数个。因此我们要做一个求模\(2\)意义下方案数的0/1背包，注意到模\(2\)加法其实就是异或了，因此用bitset维护状态数组，每次读进来一个数左移再异或即可完成转移。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
const int maxs = 2000001;
std::bitset<maxs> S;
int main() {
  S[0] = 1;
  int n; scanf("%d", &n);
  for(int i = 1; i <= n; i ++) {
    int x; scanf("%d", &x);
    S ^= (S << x);
  }
  int ans = 0;
  for(int i = 1; i < maxs; i ++) {
    if(S[i]) ans ^= i;
  }
  printf("%d\n", ans);
  return 0;
}