Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

 
 
 
 
General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
107759003 Practice:
kotatsugame
1006F - 23 C++17 (GCC 9-64) Accepted 2760 ms 237184 KB 2021-02-18 12:08:38 2021-02-18 12:08:38
→ Source
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int N,M;
long long K,A[20][20];
vector<long long>T[10],V[10];
vector<long long>dp[10];
vector<long long>ep[10];
int N1,N2;
main()
{
	scanf("%d%d%lld",&N,&M,&K);
	for(int i=0;i<N;i++)for(int j=0;j<M;j++)scanf("%lld",&A[i][j]);
	if(N==1)
	{
		for(int j=0;j<M;j++)K^=A[0][j];
		puts(K?"0":"1");
		return 0;
	}
	N1=N/2;N2=N-N1;
	{
		dp[0].push_back(0);
		for(int j=0;j<(M+1)/2;j++)
		{
			for(int i=0;i<N1;i++)
			{
				for(long long&a:dp[i])a^=A[i][j];
			}
			for(int i=0;i<N1-1;i++)
			{
				for(long long a:dp[i])dp[i+1].push_back(a^A[i+1][j]);
			}
			T[j]=dp[N1-1];
			sort(T[j].begin(),T[j].end());
		}
	}
	{
		ep[0].push_back(K);
		for(int jj=0;jj<(M+1)/2;jj++)
		{
			int j=M-jj-1;
			for(int i=0;i<N2;i++)
			{
				for(long long&a:ep[i])a^=A[N-i-1][j];
			}
			for(int i=0;i<N2-1;i++)
			{
				for(long long a:ep[i])ep[i+1].push_back(a^A[N-i-2][j]);
			}
			V[jj]=ep[N2-1];
			sort(V[jj].begin(),V[jj].end());
		}
	}
	long long ans=0;
	{
		for(int j=(M+1)/2;j<M;j++)
		{
			for(int i=0;i<N1;i++)
			{
				for(long long&a:dp[i])a^=A[i][j];
			}
			for(int i=0;i<N1-1;i++)
			{
				for(long long a:dp[i])dp[i+1].push_back(a^A[i+1][j]);
			}
			sort(dp[N1-1].begin(),dp[N1-1].end());
			int id=0;
			for(int i=0;i<dp[N1-1].size();)
			{
				int k=i;
				while(k<dp[N1-1].size()&&dp[N1-1][i]==dp[N1-1][k])k++;
				int d=k-i;
				while(id<V[M-j-1].size()&&V[M-j-1][id]<dp[N1-1][i])id++;
				if(id<V[M-j-1].size()&&V[M-j-1][id]==dp[N1-1][i])
				{
					int jd=id;
					while(jd<V[M-j-1].size()&&V[M-j-1][id]==V[M-j-1][jd])jd++;
					ans+=(long long)d*(jd-id);
					id=jd;
				}
				i=k;
			}
		}
	}
	{
		for(int jj=(M+1)/2;jj<M;jj++)
		{
			int j=M-jj-1;
			for(int i=0;i<N2;i++)
			{
				for(long long&a:ep[i])a^=A[N-i-1][j];
			}
			for(int i=0;i<N2-1;i++)
			{
				for(long long a:ep[i])ep[i+1].push_back(a^A[N-i-2][j]);
			}
			sort(ep[N2-1].begin(),ep[N2-1].end());
			int id=0;
			for(int i=0;i<ep[N2-1].size();)
			{
				int k=i;
				while(k<ep[N2-1].size()&&ep[N2-1][i]==ep[N2-1][k])k++;
				int d=k-i;
				while(id<T[M-jj-1].size()&&T[M-jj-1][id]<ep[N2-1][i])id++;
				if(id<T[M-jj-1].size()&&T[M-jj-1][id]==ep[N2-1][i])
				{
					int jd=id;
					while(jd<T[M-jj-1].size()&&T[M-jj-1][id]==T[M-jj-1][jd])jd++;
					ans+=(long long)d*(jd-id);
					id=jd;
				}
				i=k;
			}
		}
	}
	if(M%2==1)
	{
		int id=0;
		for(int i=0;i<T[M/2].size();)
		{
			int k=i;
			while(k<T[M/2].size()&&T[M/2][i]==T[M/2][k])k++;
			int d=k-i;
			while(id<V[M/2].size()&&V[M/2][id]<T[M/2][i])id++;
			if(id<V[M/2].size()&&V[M/2][id]==T[M/2][i])
			{
				int jd=id;
				while(jd<V[M/2].size()&&V[M/2][id]==V[M/2][jd])jd++;
				ans+=(long long)d*(jd-id);
				id=jd;
			}
			i=k;
		}
	}
	printf("%lld\n",ans);
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details