Advertisement
KShah

Untitled

Mar 22nd, 2022
1,402
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.95 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using std::cin;
  5. using std::cout;
  6. using std::vector;
  7.  
  8. const long long MOD = 1e9 + 7;
  9.  
  10. long long bit(long long mask, long long pos) {
  11.   return (mask >> pos) & 1;
  12. }
  13.  
  14. long long bits_neighbours(long long mask, long long n) {
  15.   for (long long i = 0; i < n - 1; ++i) {
  16.     if (bit(mask, i) == bit(mask, i + 1)) {
  17.       return true;
  18.     }
  19.   }
  20.   return false;
  21. }
  22.  
  23. int main() {
  24.   long long n, m;
  25.   cin >> n >> m;
  26.   vector<vector<char> > table(n, vector<char>(m));
  27.   for (long long i = 0; i < n; ++i) {
  28.     for (long long j = 0; j < m; ++j) {
  29.       cin >> table[i][j];
  30.     }
  31.   }
  32.  
  33.   vector<long long> mask_and(m);
  34.   vector<long long> mask_or(m);
  35.  
  36.   for (long long i = 0; i < m; ++i) {
  37.     long long to_and = ~0;
  38.     long long to_or = 0;
  39.     for (long long j = 0; j < n; ++j) {
  40.       if (table[j][i] == '+') {
  41.         to_or = to_or | (1 << j);
  42.       }
  43.       if (table[j][i] == '-') {
  44.         to_and = to_and & ~(1 << j);
  45.       }
  46.     }
  47.     mask_and[i] = to_and;
  48.     mask_or[i] = to_or;
  49.   }
  50.  
  51.   const long long deg = 1 << n;
  52.   const long long ones = (1 << n) - 1;
  53.  
  54.   vector<vector<long long> > dp(m, vector<long long>(deg));
  55.   for (long long mask = 0; mask < 1 << n; ++mask) {
  56.     long long new_mask = (mask | mask_or[0]) & mask_and[0];
  57.     dp[0][new_mask] = 1;
  58.   }
  59.  
  60.   for (long long i = 1; i < m; ++i) {
  61.     for (long long msk = 0; msk < deg; ++msk) {
  62.       long long mask = (msk | mask_or[i]) & mask_and[i];
  63.       if (bits_neighbours(mask, n)) {
  64.         dp[i][mask] = dp[i - 1][mask ^ ones] % MOD;
  65.       } else {
  66.         dp[i][mask] = (dp[i - 1][mask] + dp[i - 1][mask ^ ones]) % MOD;
  67.       }
  68.     }
  69.   }
  70.  
  71.   long long sum = 0;
  72.   vector<bool> used(deg, 0);
  73.   for (long long i = 0; i < deg; ++i) {
  74.     long long mask = (i | mask_or[m - 1]) & mask_and[m - 1];
  75.     if (!used[mask]) {
  76.       used[mask] = true;
  77.       sum = (sum + dp[m - 1][mask]) % MOD;
  78.     }
  79.   }
  80.  
  81.   cout << sum << "\n";
  82.  
  83.   return 0;
  84. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement