BZOJ 3687: 简单题(dp+bitset)

传送门

解题思路

　　设(f(i))表示和为(i)时的方案数，那么转移方程为(f(i)+=f(i-x))，(x)为当前枚举到的数字，这样做是(O(nsum a_i))的，考虑优化。发现最后要的并不是方案数，最后的奇偶性，那么转移方程转化为(f(i)^=f(i-x))，这样可以用(bitset)优化，时间复杂度(O(frac{n sum a_i}{32}))。

代码

#include<iostream>
#include<cstdio>
#include<bitset>

using namespace std;
const int N=2000005;

int n,sum,ans;
bitset<N> f;

int main(){
	scanf("%d",&n); int x;
	f[0]=1;
	for(int i=1;i<=n;i++) {
		scanf("%d",&x); sum+=x;
		f=(f^(f<<x));
	}
	for(int i=1;i<=sum;i++)
		if(f[i]) ans^=i;
	printf("%d
",ans);
	return 0;	
}