fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3.  
  4. using namespace std;
  5. using namespace __gnu_pbds;
  6.  
  7. #define len(x) ((int)(x).size())
  8. #define x first
  9. #define y second
  10.  
  11. using ll = long long;
  12. using llu = unsigned long long;
  13. using lld = long double;
  14.  
  15. const int NM = 25;
  16.  
  17. int n, m;
  18. ll k, a[NM][NM];
  19. const ll TIME = chrono::high_resolution_clock::now().time_since_epoch().count();
  20. const ll SEED = (ll)(new ll);
  21. const ll RANDOM = TIME ^ SEED;
  22. const ll MOD = (int)1e9+7;
  23.  
  24. struct chash{
  25.     int operator()(ll x) const { return std::hash<int>{}((x ^ RANDOM) % MOD); }
  26. };
  27.  
  28. gp_hash_table<ll, int, chash> mp[NM][NM];
  29.  
  30. void right_bottom(int i, int j, int tot, ll mask = 0){
  31. 	if(i >= n || j >= m) return;
  32.  
  33. 	mask ^= a[i][j];
  34. 	if(i + j == tot){
  35. 		mp[i][j][mask]++;
  36. 		return;
  37. 	}
  38. 	right_bottom(i + 1, j, tot, mask);
  39. 	right_bottom(i, j + 1, tot, mask);
  40. }
  41.  
  42. ll left_up(int i, int j, int tot, ll mask = 0){
  43. 	if(i < 0 || j < 0) return 0;
  44.  
  45. 	if(n + m - i - j - 2 == tot){
  46. 		if(mp[i][j].find(k ^ mask) == mp[i][j].end()) return 0;
  47. 		return mp[i][j][k ^ mask];
  48. 	}
  49. 	mask ^= a[i][j];
  50. 	return left_up(i - 1, j, tot, mask) + left_up(i, j - 1, tot, mask);
  51. }
  52.  
  53. int main(){
  54. 	scanf("%d %d %lld", &n, &m, &k);
  55. 	for(int i = 0; i < n; i++){
  56. 		for(int j = 0; j < m; j++){
  57. 			scanf("%lld", &a[i][j]);
  58. 		}
  59. 	}
  60. 	int total_len = n + m - 2;
  61. 	right_bottom(0, 0, total_len/2);
  62. 	printf("%lld\n", left_up(n - 1, m - 1, total_len - total_len/2));
  63.  
  64. 	return 0;
  65. }
Success #stdin #stdout 0s 4388KB
comments (?)
stdin
copy 
3 4 2
1 3 3 3
0 3 3 2
3 0 1 1
stdout
copy 
5
https://ideone.com/KaZwZn
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!