?
# | 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 |
#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); }
?
?
?
?