BZOJ 3687 简单题

发布于 2017-06-12  242 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3687

题意:给出一个 n 个元素,不满足互异性的数集,求子集的算术和的异或和...


直接考虑子集是指数级复杂度的... 然而子集的算术和的个数是可以保证的。

我们知道一个数连续异或自身偶数次答案为 0 奇数次答案为自身,所以一个算术和只能为答案做出 0 或自身的贡献。用 a[i] 记录 i 这个算术和出现奇数次或偶数次,显然 bool 类型即可。

考虑转移过程 a[i]=a[i-a[j]]+a[i]

由于 dp 背包是伪多项式复杂度 O(nV).... 所以显然直接搞是不行的... 发现 a[i] 是 bool 类型 考虑利用 bitset 优化 左移搞一搞即可
结果跑的还是很慢...rk1 是怎么搞的呀...

 


一个非常弱的准退役OIER