Raslboyy

75A

Oct 2nd, 2019
147
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.95 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <numeric>
  5.  
  6. using namespace std;
  7.  
  8. typedef long long ll;
  9.  
  10. bool bit(ll var, int pos) {
  11.     return ((var >> pos) & 1);
  12. }
  13.  
  14. int main() {
  15.     ifstream fin("input.txt");
  16.     ofstream fout("output.txt");
  17.  
  18.     int n, m; fin >> n >> m;
  19.     if (n > m)
  20.         swap(n, m);
  21.     vector<vector<ll>> dp(m, vector<ll>(1 << n));
  22.     for (int i = 0; i < (1 << n); i++) dp[0][i] = 1;
  23.     for (int i = 0; i < m - 1; i++) {
  24.         for (int prof = 0; prof < (1 << n); prof++) {
  25.             for (int next_prof = 0; next_prof < (1 << n); next_prof++) {
  26.                 bool f = 1;
  27.                 for (int k = 0; k < n - 1; k++)
  28.                     if (bit(prof, k) == bit(next_prof, k) && bit(next_prof, k) == bit(prof, k + 1) && bit(prof, k + 1) == bit(next_prof, k + 1)) {
  29.                         f = 0; break;
  30.                     }
  31.  
  32.                 dp[i + 1][next_prof] += dp[i][prof] * f;
  33.             }
  34.         }
  35.     }
  36.     fout << accumulate(dp[m - 1].begin(), dp[m - 1].end(), 0) << endl;
  37.  
  38.     fin.close();
  39.     fout.close();
  40.     return 0;
  41. }
Advertisement
Add Comment
Please, Sign In to add comment