题目梗概
给定
n
个数字，求所有区间和的异或值。
解题思路
我首先想到的就是一个动态规划，f[i]表示加和为i出现的次数。 我们考虑加入
x
，那么可以得到f[i x]=f[i x] f[i](分别表示x取或不取的情况) 因为最后需要我们求异或值，一个数异或两次等于没有异或，所以我们可以把
f[i+x]
和
f[i]
异或起来（因为异或就是不进位的加法嘛），如果用
bitset
的话就是
F=(F<<x)xor
x
<script type="math/tex" id="MathJax-Element-102">x</script>。
#include<cstdio>
#include<bitset>
using namespace std;
bitset<2000005> S;
int n,x,ans;
int main(){
freopen(
"exam.in",
"r",stdin);
freopen(
"exam.out",
"w",stdout);
scanf(
"%d",&n);
S[
0]=
1;
for (
int i=
1;i<=n;i++){
scanf(
"%d",&x);
S=(S<<x)^S;
}
for (
int i=
0;i<
2000005;i++)
if (S[i]) ans^=i;
printf(
"%d\n",ans);
return 0;
}
