Submission #19700024


Source Code Expand

Copy
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
#define N 10001000
const int mod=1e9+7;
const int mx=(1<<20)-1;
typedef long long ll;
inline ll read(){
	ll x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*f;
}
int n,a[N],p,ans,s[N],m,dp[N];
vector<int> vec[N];
int main(){
	n=read();
	s[0]=1;
	for(int i=1;i<=n;++i){
		a[i]=read();
		p^=a[i];
		s[i]=s[i-1]+(p==0);
		vec[p].push_back(i);
	}
	for(int u=1;u<=mx;++u){
		if(vec[u].empty())continue;
		if(p&&p^u)continue;
		int sum=0,qwq=0;
		for(int i=0;i<(int)vec[u].size();++i){
			dp[i]=(1LL*sum*s[vec[u][i]]-qwq+mod+1)%mod;
			sum=(sum+dp[i])%mod;
			qwq=(qwq+1LL*dp[i]*s[vec[u][i]])%mod;
		}
		cerr<<dp[vec[u].size()-1]<<endl;
		ans=(ans+(p?dp[vec[u].size()-1]:sum))%mod;
	}
	if(!p){
		int tmp=1;
		for(int i=1;i<s[n]-1;++i){
			(tmp<<=1)%=mod;
		}
		ans=(ans+tmp)%mod;
	}
	printf("%d\n",ans);
	return 0;
}



Submission Info

Submission Time
Task E - XOR Partitioning
User luogu_bot1
Language C++ (GCC 9.2.1)
Score 800
Code Size 1078 Byte
Status AC
Exec Time 1033 ms
Memory 251004 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 800 / 800
Status
AC × 4
AC × 36
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
All max_01.txt, max_02.txt, max_03.txt, max_04.txt, max_05.txt, max_06.txt, max_dence_01.txt, max_dence_02.txt, max_dence_03.txt, max_dence_04.txt, max_nonzero_01.txt, max_nonzero_02.txt, max_nonzero_03.txt, max_nonzero_04.txt, max_x_01.txt, max_x_02.txt, max_x_03.txt, max_x_04.txt, rand_01.txt, rand_02.txt, rand_03.txt, rand_04.txt, rand_05.txt, rand_06.txt, rand_07.txt, rand_08.txt, rand_09.txt, rand_10.txt, rand_11.txt, rand_12.txt, rand_13.txt, rand_14.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
Case Name Status Exec Time Memory
max_01.txt AC 173 ms 243460 KB
max_02.txt AC 1032 ms 250904 KB
max_03.txt AC 1026 ms 250988 KB
max_04.txt AC 1029 ms 250896 KB
max_05.txt AC 1025 ms 251004 KB
max_06.txt AC 1033 ms 250944 KB
max_dence_01.txt AC 179 ms 244080 KB
max_dence_02.txt AC 180 ms 243860 KB
max_dence_03.txt AC 179 ms 244032 KB
max_dence_04.txt AC 181 ms 244424 KB
max_nonzero_01.txt AC 179 ms 244008 KB
max_nonzero_02.txt AC 180 ms 244744 KB
max_nonzero_03.txt AC 180 ms 244428 KB
max_nonzero_04.txt AC 180 ms 244224 KB
max_x_01.txt AC 189 ms 246184 KB
max_x_02.txt AC 194 ms 246396 KB
max_x_03.txt AC 190 ms 246164 KB
max_x_04.txt AC 188 ms 245984 KB
rand_01.txt AC 970 ms 249928 KB
rand_02.txt AC 419 ms 241924 KB
rand_03.txt AC 554 ms 243956 KB
rand_04.txt AC 396 ms 241492 KB
rand_05.txt AC 681 ms 245744 KB
rand_06.txt AC 406 ms 241668 KB
rand_07.txt AC 228 ms 249776 KB
rand_08.txt AC 802 ms 247516 KB
rand_09.txt AC 390 ms 241544 KB
rand_10.txt AC 808 ms 247768 KB
rand_11.txt AC 199 ms 245784 KB
rand_12.txt AC 930 ms 249344 KB
rand_13.txt AC 174 ms 241128 KB
rand_14.txt AC 191 ms 243488 KB
sample_01.txt AC 160 ms 237900 KB
sample_02.txt AC 159 ms 237972 KB
sample_03.txt AC 160 ms 238028 KB
sample_04.txt AC 162 ms 238128 KB