[BZOJ2687]简单题（dp+bitset优化）

题目描述

传送门

题解

刚开始想的有问题，因为很多子集和可能为同一个数 f(i)表示和为i的子集一共有多少个，那么每加进一个数x，f(i+x)+=f(i) 这样的话时间是O((∑ai)2)$O((/sum a_i)^2)$的，考虑怎么优化 很显然最终的答案只与f的奇偶有关，那么让f(i)表示和为i的子集的个数%2的值 转移就变成了f(i+x)^=f(i) 可以把整个f看成一个二进制数，这样就是左移一下然后做异或 直接搞成二进制数太大了，用bitset搞一下就行了

代码