XOR Partitioning

这题也好难诶!!!好叭可能只是对于我.因为dp方程不是我写的,网上也没注释..

首先满足子区间异或和相等且当形式为 A 0 A 0 A 0..这种形式的异或前缀和才行.

so?这题就做完了,我们进行dp即可.

令dp为现在出现位子i值为A的区间的种数,很明显,当前出现假如为A,那么它可以和前面的一起转移,就是把j+1~i这段的异或值是0,跟j一起合并成一个区间进行转移.因为上一个区间已经转移了所有区间,所以其实就是在上一个区间转移即可.

还有就是不利用前面的段进行转移,而是利用i-1到i这个区间的0进行转移,可以看成是拆分成$[j+1,0][j+1,0]$,$[0+1,i][0+1,i]$,然后就需要对前面所有$f_{i}f\_i$进行转移.

所以总的来说就是嫁接和拆分.

所以有dp方程.

$f_i=f_{i-1}+su{m}_{i-1}\ast cnt{0}_{i-1,i}f\_i=f\_\{i-1\}+sum\_\{i-1\}*cnt0\_\{i-1,i\}$.

对于$a_{n}a\_n$=0需要进行特判~~因为最后一个区间还没转移呢!!当然它也只能在前面的区间.

ok这样就做完了,下次应该自己能写出来叭huah爷太强了叭.

仔细想想又似乎很清晰,可能写少了.但是我也不得不说它们代码没什么可读性.

code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int mod=1e9+7;
const int N=5e5+5;
const int M=21;

ll f,sum;
int cnt0[N],a[N];
vector<int>pos[1<<M];

int cnt(int l,int r)
{
	return cnt0[r]-cnt0[l-1];
}

void run()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		a[i]^=a[i-1];
		cnt0[i]=cnt0[i-1]+(a[i]==0);
		pos[a[i]].push_back(i);
	}
	ll ans=0;
	for(int i=0;i<(1<<20);i++)
	{
		int sz=(int)pos[i].size();
		if(!sz)		continue;
		if(a[n]!=0&&a[n]!=i)	continue;
		sum=1,f=1;
		for(int j=1;j<sz;j++)
		{
			if(i==0)	f=f*2%mod;
			else
			{
				f=(f+sum*cnt(pos[i][j-1],pos[i][j])%mod)%mod;
				sum=(sum+f)%mod;
			}
		}
		if(a[n]==0&&i==0)	ans+=f,ans%=mod;
		else if(a[n]==0)	ans+=sum,ans%=mod;
		else				ans+=f,ans%=mod;
	}
	printf("%lld\n",ans);
}
 
int main()
{
	int T=1;
//	scanf("%d",&T);
	while(T--)	run(); 
	return 0;
}
/*


*/