法一：枚举所有子集

$O(2^n)$ 肯定过不了

法二：dp计数

注意到 $∑a_i≤2000000$ 可以用背包dp记录每一个和出现的次数 设 $dp_{i,j}$ 为前 $i$ 个数中出现一个子集和为 $j$ 的方案数，可以看做01背包，于是得到转移方程：

if (j>=a[i]) f[i][j]+=f[i-1][j-a[i]];
f[i][j]+=f[i-1][j];

但是空间太大，考虑滚动数组：

for (int i=1;i<=n;i++){
		for (int j=2000000;j>=a[i];j--){//倒着
			f[j]+=f[j-a[i]];
		}
	}

进一步优化空间：因为 $xor$ 的性质，我们只需要知道这个数出现的次数是奇数还是偶数，于是将 $f_{i,j}$ 设为 $bool$ 类型

f[j]+=f[j-a[i]] -> f[j]^=f[j-a[i]]

可是时间也很大，注意到转移方程中只有位运算，于是可以用 $bitset$ 优化（不了解bitset的戳这里）

f[j]^=f[j-a[i]] -> f=f^(f<<a[i]);

AC代码很短

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

using namespace std;

int n,a[1003],ans;
bitset<2000006> f;

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

奇怪的优化（来自dalao kkksc03wzl）

sort(a+1,a+n+1);
f[0]=1;
for (int i=1;i<=n;i++){
  sum+=a[i];
  for (int j=sum;j>=a[i];j--){
		f[j]^=f[j-a[i]];
  }
}

先排序，能使 $sum$ 增长的速度减慢，跑不满 $O(n∑a_i)$

能不能把他hack掉

简单题 题解

题意简述

求一个集合的子集和的异或和。

思路

20pts

dfs暴力枚举每一个子集，计算每个子集的和，异或到ans里。

O(2^n)的时间复杂度，悲 。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,ans,a[1007];
void dfs(int x,int add){
	if(x==n+1){
		ans^=add;
		return;
	}
	dfs(x+1,add+a[x]);
	dfs(x+1,add);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i = 1;i<=n;i++)cin>>a[i];
	dfs(1,0);
	cout<<ans<<'\n';
	return 0;
}

DP

设dp[i][j]表示前i个数中出现子集和为j的方案数，因为只有放与不放两种可能，所以当成01背包来做。

But根据本题数据规模，开不了那么大的数组，所以要滚动数组。

for (int i = 1;i<=n;i++)
	for (int j = 2000000;j>=a[i];j--)
		dp[j]+=dp[j-a[i]];

神秘 非常厉害的优化

让a[]一开始变化的尽量慢一点。

sort(a+1,a+1+n);

正解

由于是异或操作，自己xor自己=0，所以可以统计每个数出现的次数。若为奇数，则对最终答案有贡献；否则抵消，贡献为0。

接下来，bitset优化

知识👉：百度百科， OI-WIKI—bitset

用bitset记录某个数是否在子集和中出现，对二进制进行移位。 重点是出现个数的奇偶性！

CODE

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a,add,ans;
bitset<2000007>b;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	b[0]=1;//！！！ 
	for(int i = 1;i<=n;i++){
		cin>>a,add+=a;
		b^=(b<<a);
	}
	for(int i = 1;i<=add;i++)if(b[i])ans^=i;
	cout<<ans<<'\n';
	return 0;
}

洛谷：U360643 灵茶八题 - 子序列 +w^

题目概括：

长度为n的序列，所有子集的算术和的异或和 1<n<1000，∑ai ≤2000000。

暴力枚举（20pts）：

dfs枚举所有子集，复杂度O(2^n^)

动态规划(100pts) :

设dp[i][j]为：前i个数，和为j的子集个数

ll dp[1010][2000010];

显然会爆空间。所以滚动一下变成dp[j]。

ll dp[2000010];

当dp[i][j]为偶数时时，j和ans异或了偶数次（这不啥用没有嘛） 所以真正对答案产生影响的，是dp[i][j]为奇数的子集。聪明的你一定发现了，dp[i][j]的值跟ans没有关系，只有奇偶性有用，可以用异或（^）。

代码如下：

dp[0] = 1;
for (ll i=1; i<=n; i++) {
	cin>>x;
	for (ll j=N-1; j>=x; j--)
		dp[j] = dp[j]^dp[j-x];
}

用bitset优化空间：

for (ll i=1; i<N; i++)
	dp = dp^(dp<<a[i]);

赛时只写了20分暴力（逃）

$n<1000$ 所以 $2^n$ 肯定跑不过 注意到 $∑ai≤2000000$ ，我们考虑统计每个子集可能出现的和的方案数，这个可以用dp统计 $f[i][j]=f[i-1][j]+f[i-1][j-a[i]]$ 即前 $i$ 个数组成 $j$ 的方案数。

又因为题目要求的是所有子集的算术和的异或和，所以我们只需判断 $f[i][j]$ 的奇偶性就可以 然后 $f[i][j]$ 的第二维可以倒叙枚举 $j$ 压去，式子就会变为 $f[j]=f[j]+f[j-a[i]]$

但是这个时间复杂度还是过不去的，又因为我们只用统计奇偶性，所以我们能够想到 $bitset$ 优化

正解：

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10;

int n, a[N], m;

bitset<2000001> f;

void read() {
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		m += a[i];
	}
	return ;
}

void compute() {
	f[0] = 1;
	for(int i = 1; i <= n; i++) 
		f = (f ^ (f << a[i]));
	int ans = 0;
	for(int i = 1;i <= m; i++)
		if(f[i]) ans ^= i;
	cout << ans;
	return ;
}

int main() {
	read();
	compute();
	return 0;
}