API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Aug 21st, 2019
125
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 9.16 KB | None | 0 0
raw download clone embed print report
  1. #include <bits/stdc++.h>
  2. #pragma GCC optimize("Ofast")
  3. #pragma GCC target("sse,sse2,sse3,ssse3,sse4")
  4. #define mp make_pair
  5. #define mt make_tuple
  6. #define all(x) (x).begin(), (x).end()
  7. #define rall(x) (x).rbegin(), (x).rend()
  8. #define sz(x) int((x).size())
  9.  
  10. using namespace std;
  11.  
  12. //typedef __int128 vll;
  13.  
  14. mt19937 gen_rand;
  15.  
  16. /*OUTPUT*/
  17. /*PAIR*/
  18. /*
  19. void read(vll &x) {
  20.     string s;
  21.     cin >> s;
  22.     x = 0;
  23.     int buf = 1;
  24.     for (auto c : s) {
  25.         if (c == '-') {
  26.             assert(buf != -1);
  27.             buf = -1;
  28.             continue;
  29.         }
  30.         x *= 10;
  31.         x += (c - '0');
  32.     }
  33.     x *= buf;
  34. }
  35.  
  36. ostream &operator<<(ostream &os, vll x) {
  37.     deque<char> res;
  38.     int buf = 0;
  39.     if (x < 0) {
  40.         buf = 1;
  41.         x = -x;
  42.         res.push_back('-');
  43.     }
  44.     bool flag = false;
  45.     while (x > 0 || !flag) {
  46.         flag = true;
  47.         res.push_back(char('0' + x % 10));
  48.         x /= 10;
  49.     }
  50.     reverse(res.begin() + buf, res.end());
  51.     for (auto c : res) {
  52.         os << c;
  53.     }
  54.     return os;
  55. }
  56. */
  57.  
  58. template<typename T, typename U>
  59. ostream &operator<<(ostream &os, pair<T, U> &a) {
  60.     os << "(";
  61.     os << a.first << ", ";
  62.     os << a.second;
  63.     os << ")";
  64.     return os;
  65. }
  66. /*PAIR*/
  67.  
  68. /*ARR*/
  69. template<typename T>
  70. ostream &operator<<(ostream &os, vector<T> &a) {
  71.     os << "{";
  72.     bool was = false;
  73.     for (auto &x: a) {
  74.         if (was) {
  75.             os << ", ";
  76.         }
  77.         was = true;
  78.         os << x;
  79.     }
  80.     os << "}";
  81.     return os;
  82. }
  83. /*ARR*/
  84. /*OUTPUT*/
  85.  
  86. /*DEBUG*/
  87. template<typename T>
  88. inline void debug(const char* sdbg, T x) {
  89.     cerr << "The value of " << sdbg << " is " << x << "\n";
  90. };
  91.  
  92. template<typename T, typename... U>
  93. inline void debug(const char* sdbg, T h, U... t) {
  94.     cerr << "The value of ";
  95.     while (*sdbg != ',') {
  96.         cerr << *sdbg++;
  97.     }
  98.     cerr << " is " << h << "\n";
  99.     debug(sdbg + 1, t...);
  100.     cerr << "\n";
  101. }
  102.  
  103. #define value(...) debug(#__VA_ARGS__, __VA_ARGS__)
  104. /*DEBUG*/
  105.  
  106. template<typename T>
  107. T abs(T x) {
  108.     if (x < 0) {
  109.         return -x;
  110.     } else {
  111.         return x;
  112.     }
  113. }
  114.  
  115. template<typename T>
  116. T sqr(T x) {
  117.     return x * x;
  118. };
  119.  
  120. const long long INF_FOR_SHORT_TIME = (long long)(1e9);
  121.  
  122. template<typename T>
  123. T mul(T a, T b, T m) {
  124.     if (a <= INF_FOR_SHORT_TIME && b <= INF_FOR_SHORT_TIME) {
  125.         return (a * b) % m;
  126.     }
  127.     T q = (long long)((long double)a * (long double)b / (long double)m);
  128.     T r = a * b - q * m;
  129.     return (r + 5 * m) % m;
  130. }
  131.  
  132. template<typename T, typename U>
  133. T binpow(T a, U n, T MOD) {
  134.     T res = 1;
  135.     while (n) {
  136.         if (n & 1) {
  137.             res = mul(res, a, MOD);
  138.         }
  139.         a = mul(a, a, MOD);
  140.         n >>= 1;
  141.     }
  142.     return res;
  143. };
  144.  
  145. template<typename T>
  146. int sign(T x) {
  147.     if (x < 0) {
  148.         return -1;
  149.     } else if (x > 0) {
  150.         return 1;
  151.     } else {
  152.         return 0;
  153.     }
  154. };
  155.  
  156. template<typename T>
  157. T gcd(T a, T b) {
  158.     if (a > b) {
  159.         swap(a, b);
  160.     }
  161.     while (a) {
  162.         b %= a;
  163.         swap(a, b);
  164.     }
  165.     return b;
  166. };
  167.  
  168. template<typename T>
  169. bool uin(T &a, T b) {
  170.     if (a > b) {
  171.         a = b;
  172.         return true;
  173.     }
  174.     return false;
  175. };
  176.  
  177. template<typename T>
  178. bool uax(T &a, T b) {
  179.     if (a < b) {
  180.         a = b;
  181.         return true;
  182.     }
  183.     return false;
  184. };
  185.  
  186. typedef unsigned int uint;
  187. typedef unsigned long long ull;
  188. typedef long long ll;
  189. typedef long double ld;
  190.  
  191. /*curlink v1.9 + 128*/
  192.  
  193. const int mod = int(1e9) + 7;
  194. const int N = 25;
  195. const int NUS = 271444;
  196.  
  197. int n, m, maxn;
  198.  
  199. int get(int mask, int ind) {
  200.     return (mask >> ind) & 1;
  201. }
  202.  
  203. void del(int &mask, int ind) {
  204.     if ((mask >> ind) & 1) {
  205.         mask ^= (1 << ind);
  206.     }
  207. }
  208.  
  209. int main() {
  210.     gen_rand.seed(time(0));
  211.     ios_base::sync_with_stdio(false);
  212.     cin.tie(nullptr);
  213.     cout.tie(nullptr);
  214.     cin >> n >> m;
  215.     if (n > m) {
  216.         swap(n, m);
  217.     }
  218.     if (n == 1) {
  219.         int dp[m + 1][2] = {};
  220.         dp[1][0] = 1;
  221.         dp[1][1] = 1;
  222.         for (int len = 2; len <= m; ++len) {
  223.             dp[len][0] = (dp[len - 1][0] + dp[len - 1][1]) % mod;
  224.             dp[len][1] = dp[len - 1][0];
  225.         }
  226.         cout << (dp[m][0] + dp[m][1]) % mod;
  227.         return 0;
  228.     }
  229.     maxn = (1 << (n + 1));
  230.     int us[N][NUS], mv[N][NUS], rv[N][NUS];
  231.     uint index[N];
  232.     {
  233.     vector<int> can[N + 1];
  234.     can[1].push_back(0);
  235.     can[1].push_back(1);
  236.     for (int len = 2; len <= n; ++len) {
  237.         int bt = (1 << (len - 1));
  238.         for (auto fr : can[len - 1]) {
  239.             int x = get(fr, len - 2);
  240.             if (x) {
  241.                 can[len].push_back(fr);
  242.             } else {
  243.                 can[len].push_back(fr);
  244.                 can[len].push_back(fr + bt);
  245.             }
  246.         }
  247.     }
  248.     for (int i = 0; i < n; ++i) {
  249.         for (auto mask0 : can[i + 1]) {
  250.             for (auto mask1 : can[n - i]) {
  251.                 if (get(mask0, 0) & get(mask1, 0)) {
  252.                     continue;
  253.                 }
  254.                 if (get(mask0, 1) & get(mask1, 0)) {
  255.                     continue;
  256.                 }
  257.                 if (get(mask0, 0) & get(mask1, 1)) {
  258.                     continue;
  259.                 }
  260.                 us[i][index[i]] = (mask0 + (mask1 << (i + 1)));
  261.                 int mask = (mask0 + (mask1 << (i + 1)));
  262.                 int nw = mask;
  263.                 for (int k = i + 2; k <= n; ++k) {
  264.                     del(nw, k - 1);
  265.                     nw += (1 << (k - 1)) * get(nw, k);
  266.                 }
  267.                 del(nw, n);
  268.                 nw <<= 1;
  269.                 mv[i][index[i]] = (nw);
  270.                 nw = 0;
  271.                 int ct = 1;
  272.                 for (int k = n - 1; k >= 0; --k) {
  273.                     int x = get(mask, k);
  274.                     if (x) {
  275.                         nw ^= (1 << ct);
  276.                     }
  277.                     ++ct;
  278.                 }
  279.                 rv[i][index[i]] = (nw);
  280.                 ++index[i];
  281.             }
  282.         }
  283.     }
  284.     }
  285.     for (int i = 0; i < n; ++i) {
  286.         int nxt = (i + 1) % n;
  287.         unordered_map<int, int> pos;
  288.         for (int k = 0; k < index[nxt]; ++k) {
  289.             pos[us[nxt][k]] = k;
  290.         }
  291.         if (i + 1 < n) {
  292.             for (int k = 0; k < index[i]; ++k) {
  293.                 int nw = mv[i][k];
  294.                 if (pos.count(nw)) {
  295.                     rv[i][k] = pos[nw];
  296.                 } else {
  297.                     rv[i][k] = -1;
  298.                 }
  299.             }
  300.             for (int k = 0; k < index[i]; ++k) {
  301.                 int nw = mv[i][k] + 1;
  302.                 if (pos.count(nw)) {
  303.                     mv[i][k] = pos[nw];
  304.                 } else {
  305.                     mv[i][k] = -1;
  306.                 }
  307.             }
  308.         } else {
  309.             for (int k = 0; k < index[i]; ++k) {
  310.                 int nw = rv[i][k] + 1;
  311.                 if (pos.count(nw)) {
  312.                     mv[i][k] = pos[nw];
  313.                 } else {
  314.                     mv[i][k] = -1;
  315.                 }
  316.             }
  317.             for (int k = 0; k < index[i]; ++k) {
  318.                 int nw = rv[i][k];
  319.                 if (pos.count(nw)) {
  320.                     rv[i][k] = pos[nw];
  321.                 } else {
  322.                     rv[i][k] = -1;
  323.                 }
  324.             }
  325.         }
  326.     }
  327.     const int timer = -1;
  328.     int cur[NUS], nw_cur[NUS];
  329.     for (int i = 0; i < index[0]; ++i) {
  330.         cur[i] = 1;
  331.     }
  332.     int lst = 0;
  333.     for (int i = 0; i < n; ++i) {
  334.         if (i + 1 < n) {
  335.             for (int k = 0; k < index[i]; ++k) {
  336.                 int mask = us[i][k];
  337.                 if (get(mask, 0) || get(mask, i + 1) || get(mask, i + 2) || get(mask, i + 3)) {
  338.                     mv[i][k] = -1;
  339.                 }
  340.             }
  341.         } else {
  342.             for (int k = 0; k < index[i]; ++k) {
  343.                 int mask = us[i][k];
  344.                 if (get(mask, i) || (i > 0 && get(mask, i - 1))) {
  345.                     mv[i][k] = -1;
  346.                 }
  347.             }
  348.         }
  349.     }
  350.     for (int j = 1; j < m; ++j) {
  351.         for (int i = 0; i < n; ++i) {
  352.             if (i == n - 1 && j == m - 1) {
  353.                 continue;
  354.             }
  355.             int nxt = (i + 1) % n;
  356.             lst = index[nxt];
  357.             for (int k = 0; k < index[nxt]; ++k) {
  358.                 nw_cur[k] = 0;
  359.             }
  360.             if (i + 1 < n) {
  361.                 for (int k = 0; k < index[i]; ++k) {
  362.                     int mask = us[i][k];
  363.                     if (rv[i][k] != timer) {
  364.                         nw_cur[rv[i][k]] += cur[k];
  365.                         nw_cur[rv[i][k]] %= mod;
  366.                     }
  367.                     if (mv[i][k] != timer) {
  368.                         nw_cur[mv[i][k]] += cur[k];
  369.                         nw_cur[mv[i][k]] %= mod;
  370.                     }
  371.                 }
  372.             } else {
  373.                 for (int k = 0; k < index[i]; ++k) {
  374.                     int mask = us[i][k];
  375.                     if (rv[i][k] != timer) {
  376.                         nw_cur[rv[i][k]] += cur[k];
  377.                         nw_cur[rv[i][k]] %= mod;
  378.                     }
  379.                     if (mv[i][k] != timer) {
  380.                         nw_cur[mv[i][k]] += cur[k];
  381.                         nw_cur[mv[i][k]] %= mod;
  382.                     }
  383.                 }
  384.             }
  385.             swap(cur, nw_cur);
  386.         }
  387.     }
  388.     int ans = 0;
  389.     for (int i = 0; i < lst; ++i) {
  390.         ans += cur[i];
  391.         ans %= mod;
  392.     }
  393.     cout << ans;
  394.     return 0;
  395. }
  396.  
  397.     /*
  398.     vector<vector<int>> mv(maxn, vector<int>(n));
  399.     vector<vector<int>> rv(maxn, vector<int>(n));
  400.     for (int mask = 0; mask < maxn; ++mask) {
  401.         for (int i = 0; i < n; ++i) {
  402.             int nw = mask;
  403.             for (int k = i + 2; k <= n; ++k) {
  404.                 del(nw, k - 1);
  405.                 nw += (1 << (k - 1)) * get(nw, k);
  406.             }
  407.             del(nw, n);
  408.             nw <<= 1;
  409.             mv[mask][i] = nw;
  410.  
  411.             nw = 0;
  412.             int ct = 1;
  413.             for (int k = n - 1; k >= 0; --k) {
  414.                 int x = get(mask, k);
  415.                 if (x) {
  416.                     nw ^= (1 << ct);
  417.                 }
  418.                 ++ct;
  419.             }
  420.             rv[mask][i] = nw;
  421.         }
  422.     }
  423.     */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!