每日一题 Xorto

这道题开始写的时候让我想起了子段异或这道题
https://ac.nowcoder.com/acm/contest/3005/D
思路：首先你需要知道 0^x=x ; x^x=0
数据比较小(枚举啦）（我太菜了orz）
所以接下来我们枚举一个区间（求出他的异或和）然后找到其他区间（不重叠）是否存在和此前区间一样的异或和值（ x^x=0嘛） 枚举一条线将总区间分成两个区间 例如{a1,a2,a3,a4,a5}
从a1开始分成{a1}{a2，a3，a4，a5}
{a2} {a2,a3} {a2,a3,a4} {a2,a3,a4,a5}
{a3} {a3,a4} {a3,a4,a5}
这是下面代码里面的枚举法

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1007;
ll a[maxn];
ll b[maxn];///异或前缀和数组
map<ll,ll>M;///记录每个子段的异或值
int main()
 {
     ll n;
     scanf("%lld",&n);
     memset(a,0,sizeof(a));
     memset(b,0,sizeof(b));
     for (int i=1;i<=n;++i)
     {
          scanf("%lld",a+i);
          b[i]=b[i-1]^a[i];///0异或任何数都是本身，
     }
     ll ans=0;
     for (ll  i=1;i<=n;++i)///从左向右枚举
     {
          int w=0;
          for (ll  j=i;j>=1;--j)
          {
              w^=a[j];///从一个值枚举到以1-j的各个子集的异或和
              M[w]++;///储存子集异或和
          }
          w=0;
          for (ll k=i+1;k<=n;++k)
          {
              w=w^a[k];///枚举从i+1到n的子集 不会重叠因为每次异或值中的a[i]不同
              ans+=M[w];///加上满足条件的子集
          }
     }
     printf("%lld",ans);
     return 0;
}

当然可以用前缀和记录
i-j的子段用M[i-1]^M [j]就行

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1007;
ll a[maxn];
ll b[maxn];///异或前缀和数组
map<ll,ll>M;///记录每个子段的异或值
int main()
 {
     ll n;
     scanf("%lld",&n);
     memset(a,0,sizeof(a));
     memset(b,0,sizeof(b));
     for (int i=1;i<=n;++i)
     {
          scanf("%lld",a+i);
          b[i]=b[i-1]^a[i];///0异或任何数都是本身，
     }
     ll ans=0;
     ll w=0;
     for (ll i=1;i<=n;++i)
     {
         for (int j=i;j>=1;--j)
         {
             M[b[i]^b[j-1]]++;///枚举1到n
         }
         for (int k=i;k<=n-1;++k)
         {
             ans+=M[b[k+1]^b[i]];///从i+1例举到n
         }
     }
     printf("%lld",ans);
     return 0;
}