算法复习——bitset(bzoj3687简单题)

题目:

Description

小呆开始研究集合论了，他提出了关于一个数集四个问题：
1．子集的异或和的算术和。
2．子集的异或和的异或和。
3．子集的算术和的算术和。
4．子集的算术和的异或和。
目前为止，小呆已经解决了前三个问题，还剩下最后一个问题还没有解决，他决定把
这个问题交给你，未来的集训队队员来实现。

Input

第一行，一个整数n。
第二行，n个正整数，表示01，a2…．，。

Output

一行，包含一个整数，表示所有子集和的异或和。

Sample Input

2
1 3

Sample Output

HINT

【样例解释】

6=1 异或 3 异或 (1+3)

【数据规模与约定】

ai >0，1<n<1000，∑ai≤2000000。

另外，不保证集合中的数满足互异性，即有可能出现Ai= Aj且i不等于J

Source：

题解：

按照正常思路是维护一个dp[i],表示和为i的组合有多少个，然后如果dp[i]%2==1则ans^i就可以了··然而复杂度为sum*n,果断T

考虑用一个布尔数组表示dp[i]，dp[i]为1表示和为i的组合的数量为奇数，0为偶数

然后每输入一个数x，可以用dp[i]更新dp[i+x]，即dp[i+x]=(dp[i+x]+dp[i])%2,既然我们用的是布尔数组，可以利用位运算+bitset，来一次性更新所有的i而不用一一枚举sum，即dp=dp^（dp<<x）.

代码：

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<ctime>

#include<cctype>

#include<cstring>

#include<string>

#include<algorithm>

#include<bitset>

using namespace std;

const int N=2e6+;

bitset<N>dp;

int ans=,a,tot,n;

int main()

{

  //freopen("a.in","r",stdin);

  scanf("%d",&n);

  dp[]=;

  for(int i=;i<=n;i++)

  {

    scanf("%d",&a);

    tot+=a;dp^=(dp<<a);

  }

  for(int i=;i<=tot;i++)

    if(dp[i])  ans^=i;

  cout<<ans<<endl;

  return ;

}

巴特西