SHARE
TWEET

Untitled

a guest Jan 24th, 2020 59 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.  
  3. Sviatoslav Bidzilia 2019
  4. CF: anakib1
  5.  
  6. */
  7.  
  8. #include <iostream>
  9. #include <cmath>
  10. #include <algorithm>
  11. #include <stdio.h>
  12. #include <cstring>
  13. #include <string>
  14. #include <cstdlib>
  15. #include <vector>
  16. #include <bitset>
  17. #include <map>
  18. #include <chrono>
  19. #include <unordered_set>
  20. #include <unordered_map>
  21. #include <numeric>
  22. #include <queue>
  23. #include <ctime>
  24. #include <stack>
  25. #include <set>
  26. #include <list>
  27. #include <deque>
  28. #include <iomanip>
  29. #include <sstream>
  30. #include <fstream>
  31. #include <stdarg.h>
  32. #include <utility>
  33.  
  34. using namespace std;
  35.  
  36. #define pb push_back
  37. #define mp make_pair
  38. #define ll long long
  39. #define ull unisgned long long
  40. #define ld long double
  41. #define all(a) a.begin(), a.end()
  42. #define SORT(a) sort(all(a))
  43. #define pii pair<int, int>
  44. #define tii triple<int, int, int>
  45. #define e 1e-7
  46. #define PI acos(-1)
  47. #define inf 1e17
  48. #define vi vector<int>
  49. #define F first
  50. #define S second
  51. #define rng(x) for(int _ = 0; _ < (x); _++)
  52. #define rngi(i, x) for(int i = 0; i < (x); i++)
  53. #define rngsi(s, i, x) for(int i = (s); i <(x); i++)
  54. #define int long long
  55.  
  56. template<typename A, typename B, typename C>
  57. struct triple
  58. {
  59.     A X;
  60.     B Y;
  61.     C Z;
  62.     triple(A a = 0, B b = 0, C c = 0) :X(a), Y(b), Z(c) {}
  63. };
  64. template<typename A, typename B, typename C>
  65. triple<A, B, C> make_triple(A a = 0, B b = 0, C c = 0)
  66. {
  67.     return triple<A, B, C>(a, b, c);
  68. }
  69. template<typename A, typename B, typename C>
  70. bool operator<(const triple<A, B, C>& a, const triple<A, B, C>& b)
  71. {
  72.     if (a.X != b.X)
  73.         return a.X < b.X;
  74.     if (a.Y != b.Y)
  75.         return a.Y < b.Y;
  76.     return a.Z < b.Z;
  77. }
  78. template<typename T, typename SS>
  79. ostream& operator<<(ostream& ofs, const pair<T, SS>& p)
  80. {
  81.     ofs << "( " << p.F << " , " << p.S << " )";
  82.     return ofs;
  83. }
  84. template<typename T>
  85. void print(T a)
  86. {
  87.     for (auto i : a)
  88.         cout << i << ' ';
  89.     cout << '\n';
  90. }
  91. template<typename T>
  92. T max(T a, T b, T c)
  93. {
  94.     return max(a, max(b, c));
  95. }
  96. template<typename T>
  97. T min(T a, T b, T c)
  98. {
  99.     return min(a, min(b, c));
  100. }
  101. struct custom_hash
  102. {
  103.     static uint64_t splitmix64(uint64_t x)
  104.     {
  105.         x += 0x9e3779b97f4a7c15;
  106.         x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
  107.         x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
  108.         return x ^ (x >> 31);
  109.     }
  110.  
  111.     size_t operator()(uint64_t x) const
  112.     {
  113.         static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
  114.         return splitmix64(x + FIXED_RANDOM);
  115.     }
  116. };
  117. #define mod (int)(1e9 + 7)
  118. signed main()
  119. {
  120.     //freopen(".in", "r", stdin);
  121.     //freopen(".out", "w", stdout);
  122.     srand(time(NULL));
  123.     cin.tie(0);
  124.     cout.tie(0);
  125.     ios_base::sync_with_stdio(false);
  126.     /*int n, m;
  127.     for(n = 4; n < 5; n++)
  128.         for (m = 6; m <= 6; m++)
  129.         {
  130.             int ans = 0;
  131.             for (int mask = 0; mask < (1 << (n * m)); mask++)
  132.             {
  133.                 vector<vi> now(n, vi(m));
  134.                 for (int i = 0; i < n; i++)
  135.                     for (int j = 0; j < m; j++)
  136.                         now[i][j] = (mask >> (m * i + j)) & 1;
  137.                 bool ok = 1;
  138.                 for (int i = 0; i < n; i++)
  139.                     for (int j = 0; j < m; j++)
  140.                     {
  141.                         int cnt = 0;
  142.                         if (i && now[i - 1][j] == now[i][j])
  143.                             cnt++;
  144.                         if (j && now[i][j - 1] == now[i][j])
  145.                             cnt++;
  146.                         if (i < n - 1 && now[i + 1][j] == now[i][j])
  147.                             cnt++;
  148.                         if (j < m - 1 && now[i][j + 1] == now[i][j])
  149.                             cnt++;
  150.                         if (cnt > 1)
  151.                             ok = 0;
  152.                     }
  153.                 /*if (ok)
  154.                 {
  155.                     cout << '\n';
  156.                     for (auto i : now)
  157.                         print(i);
  158.                     cout << '\n';
  159.                 }
  160.                 ans += ok;
  161.             }
  162.             anss[n][m] = ans;
  163.         }
  164.     for (auto i : anss)
  165.         print(i);*/
  166.     int n, m;
  167.     cin >> n >> m;
  168.     if (n == m && m == 1)
  169.         return cout << "2\n", 0;
  170.     if (n < m)
  171.         swap(n, m);
  172.     vi f(n + 1);
  173.     vi l(n + 1);
  174.     f[1] = f[2] = 1;
  175.     l[1] = 1;
  176.     l[2] = 3;
  177.     vi r(n + 1);
  178.     r[1] = f[1] + l[1];
  179.     r[2] = f[2] + l[2];
  180.     for (int i = 3; i <= n; i++)
  181.     {
  182.         f[i] = (f[i - 1] + f[i - 2]) % mod;
  183.         l[i] = (l[i - 1] + l[i - 2]) % mod;
  184.         r[i] = (f[i] + l[i]) % mod;
  185.     }
  186.     int now = (l[n] + f[n]) % mod;
  187.     if (m == 1)
  188.         return cout << now << '\n', 0;
  189.     //cout << now << '\n';
  190.     now += 2;
  191.     for (int i = 1; i < m - 1; i++)
  192.         now = (now + r[i]) % mod;
  193.     cout << now << '\n';
  194. }
RAW Paste Data
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
Top