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. const ll MUL = (int)1e6+3;
  24.  
  25. struct chash{
  26.     ll operator()(ll x) const { return std::hash<ll>{}((x ^ RANDOM) % MOD * MUL); }
  27. };
  28.  
  29. gp_hash_table<ll, int, chash> mp[NM][NM];
  30.  
  31. void right_bottom(int i, int j, int tot, ll mask = 0){
  32. 	if(i >= n || j >= m) return;
  33.  
  34. 	mask ^= a[i][j];
  35. 	if(i + j == tot){
  36. 		mp[i][j][mask]++;
  37. 		return;
  38. 	}
  39. 	right_bottom(i + 1, j, tot, mask);
  40. 	right_bottom(i, j + 1, tot, mask);
  41. }
  42.  
  43. ll left_up(int i, int j, int tot, ll mask = 0){
  44. 	if(i < 0 || j < 0) return 0;
  45.  
  46. 	if(n + m - i - j - 2 == tot){
  47. 		if(mp[i][j].find(k ^ mask) == mp[i][j].end()) return 0;
  48. 		return mp[i][j][k ^ mask];
  49. 	}
  50. 	mask ^= a[i][j];
  51. 	return left_up(i - 1, j, tot, mask) + left_up(i, j - 1, tot, mask);
  52. }
  53.  
  54. int main(){
  55. 	scanf("%d %d %lld", &n, &m, &k);
  56. 	for(int i = 0; i < n; i++){
  57. 		for(int j = 0; j < m; j++){
  58. 			scanf("%lld", &a[i][j]);
  59. 		}
  60. 	}
  61. 	int total_len = n + m - 2;
  62. 	right_bottom(0, 0, total_len/2);
  63. 	printf("%lld\n", left_up(n - 1, m - 1, total_len - total_len/2));
  64.  
  65. 	return 0;
  66. }
Success #stdin #stdout 0s 4468KB
comments (?)
stdin
copy 
3 4 2
1 3 3 3
0 3 3 2
3 0 1 1
stdout
copy 
5
https://ideone.com/LhpILA
language:
C++14 (gcc 8.3)
created:
5 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!