Dang_Quan_10_Tin

SCREENLOCK

Mar 16th, 2022 (edited)
389
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.81 KB | None | 0 0
  1. #define task "SCREENLOCK"
  2. #include <iostream>
  3. #include <cstdio>
  4. #include <cstring>
  5. #include <queue>
  6.  
  7. using namespace std;
  8.  
  9. using ll = long long;
  10. using ld = long double;
  11.  
  12. constexpr int N = 10 + 5;
  13. int pos[3][3] = {{0, 1, 2}, {3, 4, 5}, {6, 7, 8}};
  14.  
  15. int dp[512][9];
  16.  
  17. int ans[N][N], need[N][N];
  18. int n, m;
  19. vector<int> s;
  20.  
  21. void Read()
  22. {
  23.     if (m > n)
  24.         swap(m, n);
  25. }
  26.  
  27. #define bit(i, x) (((x) >> (i)) & 1)
  28.  
  29. int Get(int m, int n)
  30. {
  31.     s.clear();
  32.  
  33.     for (int i = 0; i < m; ++i)
  34.         for (int j = 0; j < n; ++j)
  35.             s.emplace_back(pos[i][j]);
  36.  
  37.     memset(dp, 0, sizeof dp);
  38.  
  39.     int ans(0);
  40.  
  41.     for (int i = 1; i < 512; ++i)
  42.     {
  43.         if (i == (i & -i))
  44.             dp[i][__lg(i)] = 1;
  45.  
  46.         for (auto j : s)
  47.             if (bit(j, i))
  48.             {
  49.                 ans += dp[i][j];
  50.  
  51.                 for (auto t : s)
  52.                     if (!bit(t, i) && (need[j][t] == -1 || bit(need[j][t], i)))
  53.                         dp[i ^ (1 << t)][t] += dp[i][j];
  54.             }
  55.     }
  56.  
  57.     return ans;
  58. }
  59.  
  60. void Solve()
  61. {
  62.     if (ans[m][n] == 0)
  63.         ans[m][n] = Get(m, n);
  64.  
  65.     cout << ans[m][n] << "\n";
  66. }
  67.  
  68. /*
  69. 012
  70. 345
  71. 678
  72. */
  73.  
  74. void AddEdge(int x, int y, int v)
  75. {
  76.     need[x][y] = need[y][x] = v;
  77. }
  78.  
  79. void Prepare()
  80. {
  81.     memset(need, -1, sizeof need);
  82.  
  83.     AddEdge(0, 2, 1);
  84.     AddEdge(0, 8, 4);
  85.     AddEdge(0, 6, 3);
  86.     AddEdge(2, 8, 5);
  87.     AddEdge(2, 6, 4);
  88.     AddEdge(8, 6, 7);
  89.     AddEdge(1, 7, 4);
  90.     AddEdge(3, 5, 4);
  91. }
  92.  
  93. int32_t main()
  94. {
  95.     ios_base::sync_with_stdio(0);
  96.     cin.tie(0);
  97.     cout.tie(0);
  98.  
  99.     if (fopen(task ".INP", "r"))
  100.     {
  101.         freopen(task ".INP", "r", stdin);
  102.         freopen(task ".OUT", "w", stdout);
  103.     }
  104.  
  105.     Prepare();
  106.  
  107.     while (cin >> m >> n)
  108.     {
  109.         Read();
  110.         Solve();
  111.     }
  112. }
Add Comment
Please, Sign In to add comment