BZOJ 3687 简单题 题解

http://www.lydsy.com/JudgeOnline/problem.php?id=3687

题意:

求一个集合其子集的和的异或和。

考虑先不求异或和,只求其子集的和,首先会想到背包。

我们可以对于每一个数跑一遍背包,把背包能组成的数合起来。

于是就 TLE 了

为了不 TLE 我们开始撕烤,异或和是干嘛的。

哦,如果一个背包能组成的数出现了偶数次,那吗我管它干啥?

判定被组成的个数是否是偶数个,emm……

于是我们想到了 bitset。

那组合该如何解决呢?

我们将背包的 dp 柿子拿出来: (dp_j=dp_j+dp_{j-a_i})

改成 bitset 形式:(dp=dpoplus (dp<<a_i))

原文地址:https://www.cnblogs.com/lajiccf/p/12993973.html