codeforces|CF1054D Changing Array

因为数据范围是2e5级别的，所以我们考虑用异或前缀和来处理区间的异或情况。（比如说a包括b，那么我们通过异或可以知道b对于a的补区间的信息）

之后因为对任意\(a_i\)进行取反操作，会改变它和它之后的区间值（原来相等的都不相等了，原来不相等的都相等了），所以结果是我们对原先的前缀和直接取反，就可以表示对它进行取反操作之后的前缀和了。

因为不管怎么取反操作，一个位置的前缀和只有两种，那么我们显然就可以预处理出所有的值了。

然后我们可以把相同类别的放在一个map里面。（注意要避免重复，比如说010和101是一类）

之后把ans值\((==n*(n+1)/2)\)减去重复的就可以了。

因为是要求区间异或和不为0，那么转化下来的条件就是前缀和选取的两个不相等即可。

我们要求最大的个数，那么就是同一类的最好均分，用组合数算就行了。（比如说有5个010的话，分成2个010和3个101就行了）

最后注意一下要先给0类加一。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<map>

#define MAXN 200010

using namespace std;

long long ans;

int pre[MAXN];

map<int,int>m;

int n,k,x;

int main() {

	scanf("%d%d",&n,&k);

	m[0]++;

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

	{

		scanf("%d",&x);

		pre[i]=pre[i-1]^x;

		pre[i]=min(pre[i],pre[i]^((1<<k)-1));

		m[pre[i]]++;

	}

	ans=(long long)(n+1)*n/2;

	for (map<int,int>::iterator it=m.begin();it!=m.end();it++)

	{

		long long x=it->second;

		ans-=(long long)((x/2)-1)*(x/2)/2;

		ans-=(long long)((x-x/2)-1)*(x-x/2)/2;

	}

	printf("%lld\n",ans);

}

巴特西

codeforces|CF1054D Changing Array

最新文章

热门文章