API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Aug 21st, 2019
101
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 9.09 KB | None | 0 0
raw download clone embed print report
  1. #pragma GCC optimize("Ofast,no-stack-protector")
  2. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
  3. #pragma GCC optimize("unroll-loops")
  4. #pragma GCC optimize("fast-math")
  5. #pragma GCC optimize("section-anchors")
  6. #pragma GCC optimize("profile-values,profile-reorder-functions,tracer")
  7. #pragma GCC optimize("vpt")
  8. #pragma GCC optimize("rename-registers")
  9. #pragma GCC optimize("move-loop-invariants")
  10. #pragma GCC optimize("unswitch-loops")
  11. #pragma GCC optimize("function-sections")
  12. #pragma GCC optimize("data-sections")
  13. #pragma GCC optimize("branch-target-load-optimize")
  14. #pragma GCC optimize("branch-target-load-optimize2")
  15. #pragma GCC optimize("btr-bb-exclusive")
  16.  
  17. #define _CRT_SECURE_NO_WARNINGS
  18. #include <cmath>
  19. #include <cstdio>
  20. #include <cstdlib>
  21. #include <cstring>
  22. #include <ctime>
  23. #include <random>
  24. #include <algorithm>
  25. #include <bitset>
  26. #include <complex>
  27. #include <deque>
  28. #include <iomanip>
  29. #include <ios>
  30. #include <iostream>
  31. #include <iterator>
  32. #include <locale>
  33. #include <map>
  34. #include <memory>
  35. #include <new>
  36. #include <ostream>
  37. #include <queue>
  38. #include <set>
  39. #include <sstream>
  40. #include <stack>
  41. #include <string>
  42. #include <typeinfo>
  43. #include <utility>
  44. #include <valarray>
  45. #include <vector>
  46. #include <string>
  47. #include <array>
  48. #include <unordered_map>
  49. #include <unordered_set>
  50. #include <cassert>
  51.  
  52. using namespace std;
  53.  
  54. using ll = long long;
  55. using ld = long double;
  56. using itn = int;
  57. //using dd = double;
  58. mt19937 gen(41);
  59. //const dd eps = 1e-7;
  60. //const ll MAXN = 2097152;
  61. const ll INF = 1e9;
  62. //const dd pi = acos(dd(-1));
  63.  
  64. //#define endl '\n'
  65.  
  66. ll gcd(ll a, ll b) {
  67.     a = abs(a);
  68.     b = abs(b);
  69.     while (b) {
  70.         a %= b;
  71.         swap(a, b);
  72.     }
  73.     return a;
  74. }
  75.  
  76. ll binpow(ll a, ll n, ll binpow_mod = 1e9 + 7) {
  77.     ll res = 1;
  78.     while (n) {
  79.         if (n & 1)
  80.             res *= a;
  81.         a *= a;
  82.         n >>= 1;
  83.         a %= binpow_mod;
  84.         res %= binpow_mod;
  85.     }
  86.     return res;
  87. }
  88.  
  89. struct Point {
  90.     ll x, y;
  91.     bool z;
  92.     void scan() {
  93.         cin >> x >> y;
  94.     }
  95.     Point(ll X = 0, ll Y = 0, bool Z = 0) {
  96.         x = X;
  97.         y = Y;
  98.         z = Z;
  99.     }
  100.     ll operator*(Point &a) {
  101.         return x * a.y - y * a.x;
  102.     }
  103.     bool operator==(Point &a) {
  104.         return x == a.x && y == a.y;
  105.     }
  106. };
  107.  
  108. /** SOLVE
  109.  
  110. SOLVE
  111.  
  112. **/
  113.  
  114. const int mod = 1e9 + 7;
  115.  
  116. struct number {
  117.     int x = 0;
  118.     number() {
  119.         x = 0;
  120.     }
  121.     number(int X) {
  122.         x = X;
  123.     }
  124.     number operator +=(const number &a) {
  125.         x = x + a.x;
  126.         if (x > mod)
  127.             x -= mod;
  128.         return *this;
  129.     }
  130.     number operator +(const number &a) {
  131.         number c = *this;
  132.         return c += a;
  133.     }
  134.     number operator -=(const number &a) {
  135.         x = x - a.x;
  136.         if (x < 0)
  137.             x += mod;
  138.         return *this;
  139.     }
  140.     number operator -(const number &a) {
  141.         number c = *this;
  142.         return c -= a;
  143.     }
  144.     bool operator ==(number &a) {
  145.         return (x == a.x);
  146.     }
  147.     bool operator ==(int a) {
  148.         return (x == a);
  149.     }
  150. };
  151.  
  152. bool ch(ll x, ll y, ll n, ll m) {
  153.     return x >= 0 && y >= 0 && x < n && y < m;
  154. }
  155.  
  156. number check(ll n, ll m) {
  157.     number cnt = 0;
  158.     for (ll mask = 0; mask < (1 << (n * m)); mask++) {
  159.         bool f = true;
  160.         for (ll i = 0; i < n; i++) {
  161.             if (!f)
  162.                 break;
  163.             for (ll j = 0; j < m; j++) {
  164.                 if (ch(i + 1, j, n, m)) {
  165.                     if ((mask & (1 << (i * m + j))) && (mask & (1 << ((i + 1) * m + j)))) {
  166.                         f = false;
  167.                         break;
  168.                     }
  169.                 }
  170.                 if (ch(i, j + 1, n, m)) {
  171.                     if ((mask & (1 << (i * m + j))) && (mask & (1 << (i * m + j + 1)))) {
  172.                         f = false;
  173.                         break;
  174.                     }
  175.                 }
  176.                 if (ch(i + 1, j + 1, n, m)) {
  177.                     if ((mask & (1 << (i * m + j))) && (mask & (1 << ((i + 1) * m + j + 1)))) {
  178.                         f = false;
  179.                         break;
  180.                     }
  181.                 }
  182.                 if (ch(i - 1, j, n, m)) {
  183.                     if ((mask & (1 << (i * m + j))) && (mask & (1 << ((i - 1) * m + j)))) {
  184.                         f = false;
  185.                         break;
  186.                     }
  187.                 }
  188.                 if (ch(i, j - 1, n, m)) {
  189.                     if ((mask & (1 << (i * m + j))) && (mask & (1 << (i * m + j - 1)))) {
  190.                         f = false;
  191.                         break;
  192.                     }
  193.                 }
  194.                 if (ch(i - 1, j - 1, n, m)) {
  195.                     if ((mask & (1 << (i * m + j))) && (mask & (1 << ((i - 1) * m + j - 1)))) {
  196.                         f = false;
  197.                         break;
  198.                     }
  199.                 }
  200.                 if (ch(i + 1, j - 1, n, m)) {
  201.                     if ((mask & (1 << (i * m + j))) && (mask & (1 << ((i + 1) * m + j - 1)))) {
  202.                         f = false;
  203.                         break;
  204.                     }
  205.                 }
  206.                 if (ch(i - 1, j + 1, n, m)) {
  207.                     if ((mask & (1 << (i * m + j))) && (mask & (1 << ((i - 1) * m + j + 1)))) {
  208.                         f = false;
  209.                         break;
  210.                     }
  211.                 }
  212.             }
  213.         }
  214.         if (f)
  215.             cnt += 1;
  216.     }
  217.     return cnt;
  218. }
  219.  
  220. const int MAXN = 100000;
  221.  
  222. int main() {
  223. #ifdef _DEBUG
  224.     freopen("input.txt", "r", stdin);
  225.     freopen("output.txt", "w", stdout);
  226. #else
  227.     //freopen("input.txt", "r", stdin);
  228.     //freopen("output.txt", "w", stdout);
  229. #endif // DEBUG
  230.     ios_base::sync_with_stdio(false);
  231.     cin.tie(0);
  232.     cout << fixed << setprecision(20);
  233.     //-----------------------------------------------//
  234.     int n, m;
  235.     cin >> n >> m;
  236.     if (n == 1 && m == 1) {
  237.         cout << 2;
  238.         return 0;
  239.     }
  240.     if (n == 1)
  241.         swap(n, m);
  242.     if (m == 1) {
  243.         vector<int> f(n + 10);
  244.         f[1] = 1;
  245.         f[2] = 1;
  246.         for (int i = 3; i < n + 7; i++) {
  247.             f[i] = (f[i - 1] + f[i - 2]) % mod;
  248.         }
  249.         cout << f[n + 2];
  250.         return 0;
  251.     }
  252.     unordered_map<int, int> good[2], first;
  253.     good[0].max_load_factor(0.5);
  254.     good[0].reserve(MAXN);
  255.     for (int i = 0; i < 1; i++) {
  256.         good[i].max_load_factor(0.5);
  257.         good[i].reserve(MAXN);
  258.         for (int mask = 0; mask < (1 << (n + 1)); mask++) {
  259.             bool f = true;
  260.             if (!f)
  261.                 continue;
  262.             for (int j = n - i; j < n; j++) {
  263.                 if ((mask & (1 << j)) && (mask & (1 << (j + 1)))) {
  264.                     f = false;
  265.                     break;
  266.                 }
  267.             }
  268.             for (int j = 0; j < n - 1 - i; j++) {
  269.                 if ((mask & (1 << j)) && (mask & (1 << (j + 1)))) {
  270.                     f = false;
  271.                     break;
  272.                 }
  273.             }
  274.             if (!f)
  275.                 continue;
  276.             if (i == 0) {
  277.                 if ((mask & 1) && (mask & (1 << n)))
  278.                     continue;
  279.                 if (n > 1 && (mask & 2) && (mask & (1 << n)))
  280.                     continue;
  281.                 int sz = good[i].size();
  282.                 good[i][mask] = sz;
  283.             }
  284.             else {
  285.                 if ((mask & 1) && (mask & (1 << n)))
  286.                     continue;
  287.                 if (i < n - 1 && (mask & 2) && (mask & (1 << n)))
  288.                     continue;
  289.                 if ((mask & 1) && (mask & (1 << (n - 1))))
  290.                     continue;
  291.                 int sz = good[i].size();
  292.                 good[i][mask] = sz;
  293.             }
  294.         }
  295.     }
  296.     first = good[0];
  297.     int g[25][MAXN][2];
  298.     for (int i = 0; i < n; i++)
  299.         for (int j = 0; j < MAXN; j++)
  300.             for (int k = 0; k < 2; k++)
  301.                 g[i][j][k] = -1;
  302.     int kek = 1;
  303.     for (int i = 0; i < n; i++) {
  304.         kek ^= 1;
  305.         good[1 ^ kek].clear();
  306.         good[1 ^ kek].max_load_factor(0.5);
  307.         good[1 ^ kek].reserve(MAXN);
  308.         if (i != n - 1) {
  309.             i++;
  310.             for (int mask = 0; mask < (1 << (n + 1)); mask++) {
  311.                 bool f = true;
  312.                 for (int j = 0; j < n - 1 - i; j++) {
  313.                     if ((mask & (1 << j)) && (mask & (1 << (j + 1)))) {
  314.                         f = false;
  315.                         break;
  316.                     }
  317.                 }
  318.                 if (!f)
  319.                     continue;
  320.                 for (int j = n - i; j < n; j++) {
  321.                     if ((mask & (1 << j)) && (mask & (1 << (j + 1)))) {
  322.                         f = false;
  323.                         break;
  324.                     }
  325.                 }
  326.                 if (!f)
  327.                     continue;
  328.                 if (i == 0) {
  329.                     if ((mask & 1) && (mask & (1 << n)))
  330.                         continue;
  331.                     if (n > 1 && (mask & 2) && (mask & (1 << n)))
  332.                         continue;
  333.                     int sz = good[1 ^ kek].size();
  334.                     good[1 ^ kek][mask] = sz;
  335.                 }
  336.                 else {
  337.                     if ((mask & 1) && (mask & (1 << n)))
  338.                         continue;
  339.                     if (i < n - 1 && (mask & 2) && (mask & (1 << n)))
  340.                         continue;
  341.                     if ((mask & 1) && (mask & (1 << (n - 1))))
  342.                         continue;
  343.                     int sz = good[1 ^ kek].size();
  344.                     good[1 ^ kek][mask] = sz;
  345.                 }
  346.             }
  347.             i--;
  348.         }
  349.         else {
  350.             swap(good[1 ^ kek], first);
  351.         }
  352.         if (i == n - 1) {
  353.             for (auto k : good[0 ^ kek]) {
  354.                 int mask = k.first;
  355.                 int to = k.second;
  356.                 int m0 = (mask >> 1);
  357.                 int m1 = (mask >> 1) | (1 << n);
  358.                 bool f1, f2;
  359.                 f1 = mask & (2);
  360.                 f2 = mask & (4);
  361.                 if (good[1 ^ kek].count(m0))
  362.                     g[i][to][0] = good[1 ^ kek][m0];
  363.                 if (!f1 && !f2)
  364.                     if (good[1 ^ kek].count(m1))
  365.                         g[i][to][1] = good[1 ^ kek][m1];
  366.             }
  367.         }
  368.         else {
  369.             for (auto k : good[0 ^ kek]) {
  370.                 int mask = k.first;
  371.                 int to = k.second;
  372.                 int m0 = (mask >> 1);
  373.                 int m1 = (mask >> 1) | (1 << n);
  374.                 bool f1, f2, f3, f4;
  375.                 f1 = mask & (1 << n);
  376.                 f2 = mask & (1);
  377.                 f3 = mask & (2);
  378.                 if (i == n - 2)
  379.                     f4 = false;
  380.                 else
  381.                     f4 = mask & (4);
  382.                 if (good[1 ^ kek].count(m0))
  383.                     g[i][to][0] = good[1 ^ kek][m0];
  384.                 if (!f1 && !f2 && !f3 && !f4)
  385.                     if (good[1 ^ kek].count(m1))
  386.                         g[i][to][1] = good[1 ^ kek][m1];
  387.             }
  388.         }
  389.     }
  390.     int a[25][MAXN];
  391.     fill(a[0], a[0] + MAXN, 1);
  392.     for (int I = 1; I < m; I++) {
  393.         for (int j = 0; j < n; j++) {
  394.             if (I == m - 1 && j == n - 1)
  395.                 break;
  396.             fill(a[(j + 1) % n], a[(j + 1) % n] + MAXN, 0);
  397.             for (int k = 0; k < MAXN; k++) {
  398.                 if (a[j][k]) {
  399.                     for (int i = 0; i < 2; i++) {
  400.                         int to = g[j][k][i];
  401.                         if (to != -1) {
  402.                             a[(j + 1) % n][to] += a[j][k];
  403.                             if (a[(j + 1) % n][to] >= mod)
  404.                                 a[(j + 1) % n][to] -= mod;
  405.                         }
  406.                     }
  407.                 }
  408.             }
  409.             fill(a[j], a[j] + MAXN, 0);
  410.         }
  411.     }
  412.     int cnt = 0;
  413.     for (int i = 0; i < MAXN; i++) {
  414.         cnt += a[n - 1][i];
  415.         if (cnt >= mod)
  416.             cnt -= mod;
  417.     }
  418.     cout << cnt;
  419.     //-----------------------------------------------//
  420.     return 0;
  421. }
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!