Advertisement
Guest User

Untitled

a guest
Apr 28th, 2019
353
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.49 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <random>
  3.  
  4. using namespace std;
  5.  
  6. typedef unsigned long long ull;
  7. typedef long long ll;
  8. typedef long double ld;
  9. //#define int ll
  10. //#define int __int128
  11. //#define ll __int128
  12. typedef pair<int, int> pii;
  13. typedef pair<ll, ll> pll;
  14. typedef vector<int> vi;
  15. typedef vector< vi > vvi;
  16. typedef vector< vvi > vvvi;
  17. typedef vector<bool> vb;
  18. typedef vector< vb > vvb;
  19. typedef vector< vvb > vvvb;
  20. typedef vector<short> vs;
  21. typedef vector<vs> vvs;
  22. typedef vector<vvs> vvvs;
  23. typedef vector<ll> vl;
  24. typedef vector<vl> vvl;
  25. typedef vector<vvl> vvvl;
  26. typedef vector<ld> vld;
  27. typedef vector<vld> vvld;
  28. typedef vector<vvld> vvvld;
  29. typedef vector<string> vst;
  30. typedef vector<vst> vvst;
  31. typedef pair<ld, ld> pld;
  32. typedef complex<double> base;
  33.  
  34. #define inmin(a, b) a = min(a, (b))
  35. #define inmax(a, b) a = max(a, (b))
  36. #define ALL(a) a.begin(),a.end()
  37. #define RALL(a) a.rbegin(),a.rend()
  38. #define sqr(x) ((x) * (x))
  39. #define fori(i, n) for(int i = 0; i < int(n); ++i)
  40. #define SZ(a) ((int)((a).size()))
  41. #define triple(T) tuple<T, T, T>
  42. #define quad(T) tuple<T, T, T, T>
  43. #define watch(x) cerr << (#x) << " = " << (x) << endl;
  44.  
  45. #ifdef MAX_HOME
  46. #define cerr cout
  47. #else
  48. #define cerr if (false) cerr
  49. #endif
  50.  
  51. const double PI = 2 * acos(0.0);
  52. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  53. mt19937_64 rng_64(chrono::steady_clock::now().time_since_epoch().count());
  54.  
  55. const string DIGITS = "0123456789";
  56. const string ALPH = "abcdefghijklmnopqrstuvwxyz";
  57.  
  58. template <class T0, class T1>
  59. inline ostream & operator << (ostream &out, pair<T0, T1> &a) {
  60.     return out << "{" << a.first << ", " << a.second << "}";
  61. }
  62.  
  63. template <class T0, class T1, class T2>
  64. inline ostream & operator << (ostream &out, tuple<T0, T1, T2> &a) {
  65.     return out << "{" << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a) << "}";
  66. }
  67.  
  68. template <class T0, class T1, class T2, class T3>
  69. inline ostream & operator << (ostream &out, tuple<T0, T1, T2, T3> &a) {
  70.     return out << "{" << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a) << ", " <<  get<3>(a) << "}";
  71. }
  72.  
  73. template<class T>
  74. inline ostream & operator << (ostream &out, vector<T> &a) {
  75.     out << "[";
  76.     fori (i, a.size())
  77.         out << a[i] << vector<string>{", ", "]  "}[i + 1 == a.size()];
  78.     return out;
  79. }
  80.  
  81.  
  82.  
  83. void smain();
  84.  
  85. signed main() {
  86.     ios::sync_with_stdio(0);
  87.     cin.tie(0); cout.tie(0);
  88.  
  89. #ifdef MAX_HOME
  90.     freopen("input.txt", "r", stdin);
  91.     clock_t start = clock();
  92. #endif
  93.     cout << setprecision(12) << fixed;
  94.     smain();
  95. #ifdef MAX_HOME
  96.     cout << "\n\n\n\nTOTAL EXECUTION TIME: " << float( clock () - start ) /  CLOCKS_PER_SEC << endl;
  97. #endif
  98.     return 0;
  99. }
  100.  
  101. typedef bitset<2000010> bs;
  102.  
  103. int n, m;
  104. vvi dp;
  105. bs mat;
  106. const int L = 22;
  107. bs cnt[L];
  108. void smain() {
  109.  
  110.     cin >> n >> m;
  111.     dp.resize(n + 1, vi(m + 1, 0));
  112.     for (int i = 1; i <= n; ++i) {
  113.         string s;
  114.         cin >> s;
  115.         for (int j = 1; j <= m; ++j) mat[i * (m + 1) + j] = s[j - 1] == '1';
  116.     }
  117. //    cnt.resize(L, vvb(n + 1, vb(m + 1, 0)));
  118.  
  119.     fori (p, L) {
  120.         cnt[p] = mat;
  121.         for (int i = 1; i <= n; ++i) {
  122.             for (int j = 1; j <= m; ++j) {
  123.                 if (i > (1 << p))
  124.                     cnt[p][i * (m + 1) + j] = cnt[p][i* (m + 1) +j] ^
  125.                                                   cnt[p][(i - (1 << p))* (m + 1) +j];
  126.                 if (j > (1 << p))
  127.                     cnt[p][i* (m + 1) +j] = cnt[p][i* (m + 1) +j] ^
  128.                                                 cnt[p][i* (m + 1) +j - (1 << p)];
  129.                 if (i > (1 << p) && j > (1 << p))
  130.                     cnt[p][i* (m + 1) +j] = cnt[p][i* (m + 1) +j] ^
  131.                                                 cnt[p][(i - (1 << p)) * (m + 1) +j - (1 << p)];
  132.             }
  133.         }
  134.     }
  135.     for (int i = 1; i <= n; ++i) {
  136.         for (int j = 1; j <= m; ++j) {
  137.             int ans = max(dp[i - 1][j], dp[i][j - 1]);
  138.             int res = mat[i* (m + 1) +j];
  139.             if (ans < L) {
  140.                 res ^= cnt[ans][i* (m + 1) +j];
  141.             } else {
  142.                 res = 0;
  143.             }
  144.             dp[i][j] = ans + res;
  145.         }
  146.     }
  147.     vi a = {1};
  148.     fori (i, dp[n][m]) {
  149.         vi nx;
  150.         int c = 0;
  151.         for (int j = 0; j < a.size(); ++j) {
  152.             c += a[j] * 2;
  153.             nx.push_back(c % 10);
  154.             c /= 10;
  155.         }
  156.         if (c) nx.push_back(c);
  157.         a = nx;
  158.     }
  159.     for (int i = (int)a.size() - 1; i >= 0; --i) {
  160.         cout << a[i];
  161.     }
  162.  
  163. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement