Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <cstdlib>
- #include <cmath>
- #include <algorithm>
- #include <vector>
- #include <cstring>
- using namespace std;
- typedef unsigned long long ll;
- typedef long double db;
- typedef pair <int, int> pii;
- #define f first
- #define s second
- #define pb push_back
- #define mp make_pair
- const int N = 2000;
- const ll MOD = 1e18;
- struct llv
- {
- ll a[6];
- };
- llv dp[101][11][N];
- int q[11][N];
- bool e;
- int p, msk1, P;
- void sum(llv& p1, llv& p2)
- {
- for (p = 0; p < 6; p++)
- {
- p1.a[p] += p2.a[p];
- if (p1.a[p] >= MOD)
- {
- p1.a[p + 1]++;
- p1.a[p] -= MOD;
- }
- }
- }
- void print(llv nw)
- {
- e = false;
- for (p = 5; p >= 0; p--)
- {
- e |= (nw.a[p]);
- if (e) cout << nw.a[p];
- }
- if (!e) cout << 0;
- cout << endl;
- }
- int main()
- {
- int z;
- int l, w, p;
- int ni, nj, nmsk;
- cin >> l >> w;
- if (l < w) swap(l, w);
- dp[0][0][0].a[0] = 1;
- P = pow(2, w);
- for (int msk = 0; msk < P; msk++)
- {
- msk1 = msk;
- z = 0;
- while (msk1 > 0)
- {
- q[z++][msk] = msk1 % 2;
- msk1 /= 2;
- }
- }
- for (int i = 0; i < l; i++)
- for (int j = 0; j < w; j++)
- for (int msk = 0; msk < P; msk++)
- {
- 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;
- if (q[j][msk])
- {
- nmsk = msk - pow(2, j);
- sum(dp[i + (j + 1) / w][(j + 1) % w][nmsk], dp[i][j][msk]);
- continue;
- }
- if (j < w - 1)
- {
- ni = i + (j + 2) / w;
- nj = (j + 2) % w;
- if (!q[j + 1][msk])
- {
- sum(dp[ni][nj][msk + (int)pow(2, j)], dp[i][j][msk]);
- sum(dp[ni][nj][msk + (int)pow(2, j + 1)], dp[i][j][msk]);
- }
- if (q[j + 1][msk] == 1) sum(dp[ni][nj][msk + (int)pow(2, j)], dp[i][j][msk]);
- }
- if (j < w - 2)
- {
- ni = i + (j + 3) / w;
- nj = (j + 3) % w;
- 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]);
- }
- if (j > 0)
- {
- ni = i + (j + 1) / w;
- nj = (j + 1) % w;
- if (!q[j - 1][msk]) sum(dp[ni][nj][msk + (int)pow(2, j - 1) * 3], dp[i][j][msk]);
- }
- }
- print(dp[l][0][0]);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement