题解 P3917 【异或序列】

异或是一种神奇的运算，有很多种理解方法，也有很多性质。这题我们只要分开各位处理，如果在该位上某段区间有奇数个1，这段区间就贡献一个1。问题就变成处理多少段有奇数个1了。

这里的处理另一个题解Dp的思想很好，但其实不需要。这个每加入一个1时反转一下就好了。可以结合图片和代码理解。

再推荐一道同样思想的题目： XOR on Segment

本题代码如下：

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+5;

int a[N];

int main()
{
    int n,i,j;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    long long s,m,ans=0;
    for(j=0;j<30;j++){          //枚举位
        s=m=0;
        for(i=1;i<=n;i++){      //以该数结尾的序列
            if((a[i]>>j)&1)     //本数该位是1
                s=i-s;      //前面01反转
            m+=s;           //统计贡献
        }
        ans+=m*(1<<j);          //统计该位的贡献
    }
    printf("%lld",ans);
    return 0;
}