Advertisement
Guest User

Untitled

a guest
Feb 19th, 2019
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.37 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <algorithm>
  6. #include <vector>
  7. #include <cstring>
  8.  
  9. using namespace std;
  10.  
  11. typedef unsigned long long ll;
  12. typedef long double db;
  13. typedef pair <int, int> pii;
  14.  
  15. #define f first
  16. #define s second
  17. #define pb push_back
  18. #define mp make_pair
  19.  
  20. const int N = 2000;
  21. const ll MOD = 1e18;
  22.  
  23. struct llv
  24. {
  25.   ll a[6];
  26. };
  27.  
  28. llv dp[101][11][N];
  29. int q[11][N];
  30. bool e;
  31. int p, msk1, P;
  32.  
  33. void sum(llv& p1, llv& p2)
  34. {
  35.   for (p = 0; p < 6; p++)
  36.   {
  37.     p1.a[p] += p2.a[p];
  38.     if (p1.a[p] >= MOD)
  39.     {
  40.       p1.a[p + 1]++;
  41.       p1.a[p] -= MOD;
  42.     }
  43.   }
  44. }
  45.  
  46. void print(llv nw)
  47. {
  48.   e = false;
  49.   for (p = 5; p >= 0; p--)
  50.   {
  51.     e |= (nw.a[p]);
  52.     if (e) cout << nw.a[p];
  53.   }
  54.   if (!e) cout << 0;
  55.   cout << endl;
  56. }
  57.  
  58. int main()
  59. {
  60.   int z;
  61.   int l, w, p;
  62.   int ni, nj, nmsk;
  63.  
  64.   cin >> l >> w;
  65.   if (l < w) swap(l, w);
  66.  
  67.   dp[0][0][0].a[0] = 1;
  68.   P = pow(2, w);
  69.  
  70.   for (int msk = 0; msk < P; msk++)
  71.   {
  72.     msk1 = msk;
  73.     z = 0;
  74.     while (msk1 > 0)
  75.     {
  76.       q[z++][msk] = msk1 % 2;
  77.       msk1 /= 2;
  78.     }
  79.   }
  80.  
  81.   for (int i = 0; i < l; i++)
  82.     for (int j = 0; j < w; j++)
  83.       for (int msk = 0; msk < P; msk++)
  84.       {
  85.         if (dp[i][j][msk].a[0] == 0 && dp[i][j][msk].a[1] == 0 && dp[i][j][msk].a[2] == 0 && dp[i][j][msk].a[3] == 0) continue;
  86.         if (q[j][msk])
  87.         {
  88.           nmsk = msk - pow(2, j);
  89.           sum(dp[i + (j + 1) / w][(j + 1) % w][nmsk], dp[i][j][msk]);
  90.           continue;
  91.         }
  92.         if (j < w - 1)
  93.         {
  94.           ni = i + (j + 2) / w;
  95.           nj = (j + 2) % w;
  96.           if (!q[j + 1][msk])
  97.           {
  98.             sum(dp[ni][nj][msk + (int)pow(2, j)], dp[i][j][msk]);
  99.             sum(dp[ni][nj][msk + (int)pow(2, j + 1)], dp[i][j][msk]);
  100.           }
  101.           if (q[j + 1][msk] == 1) sum(dp[ni][nj][msk + (int)pow(2, j)], dp[i][j][msk]);
  102.         }
  103.         if (j < w - 2)
  104.         {
  105.           ni = i + (j + 3) / w;
  106.           nj = (j + 3) % w;
  107.           if (q[j + 1][msk] == 0 && q[j + 2][msk] == 0) sum(dp[ni][nj][msk + (int)pow(2, j) * 7], dp[i][j][msk]);
  108.         }
  109.         if (j > 0)
  110.         {
  111.           ni = i + (j + 1) / w;
  112.           nj = (j + 1) % w;
  113.           if (!q[j - 1][msk]) sum(dp[ni][nj][msk + (int)pow(2, j - 1) * 3], dp[i][j][msk]);
  114.         }
  115.       }
  116.  
  117.   print(dp[l][0][0]);
  118.  
  119.   return 0;
  120. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement