BZOJ 3687 简单题


题目链接: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 是怎么搞的呀...

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 3687 简单题


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: ,