fork(1) download
  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
stdin
3 4 2
1 3 3 3
0 3 3 2
3 0 1 1
stdout
5