[BZOJ2687]简单题(dp+bitset优化)

2/10/2017来源:ASP.NET技巧人气:837

题目描述

传送门

题解

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

代码

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<bitset> using namespace std; #define N 2000005 int n,x,sum,ans; bitset <N> f; int main() { scanf("%d",&n); f[0]=1; for (int i=1;i<=n;++i) { scanf("%d",&x); sum+=x; f^=f<<x; } for (int i=1;i<=sum;++i) if (f[i]) ans^=i; PRintf("%d\n",ans); }