Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define task "SCREENLOCK"
- #include <iostream>
- #include <cstdio>
- #include <cstring>
- #include <queue>
- using namespace std;
- using ll = long long;
- using ld = long double;
- constexpr int N = 10 + 5;
- int pos[3][3] = {{0, 1, 2}, {3, 4, 5}, {6, 7, 8}};
- int dp[512][9];
- int ans[N][N], need[N][N];
- int n, m;
- vector<int> s;
- void Read()
- {
- if (m > n)
- swap(m, n);
- }
- #define bit(i, x) (((x) >> (i)) & 1)
- int Get(int m, int n)
- {
- s.clear();
- for (int i = 0; i < m; ++i)
- for (int j = 0; j < n; ++j)
- s.emplace_back(pos[i][j]);
- memset(dp, 0, sizeof dp);
- int ans(0);
- for (int i = 1; i < 512; ++i)
- {
- if (i == (i & -i))
- dp[i][__lg(i)] = 1;
- for (auto j : s)
- if (bit(j, i))
- {
- ans += dp[i][j];
- for (auto t : s)
- if (!bit(t, i) && (need[j][t] == -1 || bit(need[j][t], i)))
- dp[i ^ (1 << t)][t] += dp[i][j];
- }
- }
- return ans;
- }
- void Solve()
- {
- if (ans[m][n] == 0)
- ans[m][n] = Get(m, n);
- cout << ans[m][n] << "\n";
- }
- /*
- 012
- 345
- 678
- */
- void AddEdge(int x, int y, int v)
- {
- need[x][y] = need[y][x] = v;
- }
- void Prepare()
- {
- memset(need, -1, sizeof need);
- AddEdge(0, 2, 1);
- AddEdge(0, 8, 4);
- AddEdge(0, 6, 3);
- AddEdge(2, 8, 5);
- AddEdge(2, 6, 4);
- AddEdge(8, 6, 7);
- AddEdge(1, 7, 4);
- AddEdge(3, 5, 4);
- }
- int32_t main()
- {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- if (fopen(task ".INP", "r"))
- {
- freopen(task ".INP", "r", stdin);
- freopen(task ".OUT", "w", stdout);
- }
- Prepare();
- while (cin >> m >> n)
- {
- Read();
- Solve();
- }
- }
Add Comment
Please, Sign In to add comment