fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_map>
  4.  
  5. using namespace std;
  6.  
  7. int n, m;
  8. const int MOD = 1e9 + 7;
  9.  
  10. // Generate all valid states for a column
  11. vector<int> generateValidStates(int n) {
  12.     vector<int> states;
  13.     int maxState = 1 << n;
  14.     for (int state = 0; state < maxState; ++state) {
  15.         // Check for vertical adjacency constraint (no two adjacent 1s)
  16.         if ((state & (state << 1)) == 0) {
  17.             states.push_back(state);
  18.         }
  19.     }
  20.     return states;
  21. }
  22.  
  23. // Precompute transitions between states
  24. unordered_map<int, vector<int>> generateTransitions(const vector<int>& states) {
  25.     unordered_map<int, vector<int>> transitions;
  26.     for (int s : states) {
  27.         for (int s_next : states) {
  28.             // Check for horizontal adjacency constraint (no overlapping 1s)
  29.             if ((s & s_next) == 0) {
  30.                 transitions[s].push_back(s_next);
  31.             }
  32.         }
  33.     }
  34.     return transitions;
  35. }
  36.  
  37. int main() {
  38.     cin >> n >> m;
  39.  
  40.     vector<int> states = generateValidStates(n);
  41.     unordered_map<int, vector<int>> transitions = generateTransitions(states);
  42.  
  43.     cout << transitions.size() << endl;
  44.  
  45.     // Initialize DP table
  46.     unordered_map<int, int> dp_current, dp_next;
  47.     for (int state : states) {
  48.         dp_current[state] = 1; // Base case: one way to reach each state in the first column
  49.     }
  50.  
  51.     // DP over columns
  52.     for (int col = 1; col < m; ++col) {
  53.         dp_next.clear();
  54.         for (auto& kv : dp_current) {
  55.             int s = kv.first;
  56.             int count = kv.second;
  57.             for (int s_next : transitions[s]) {
  58.                 dp_next[s_next] = (dp_next[s_next] + count) % MOD;
  59.             }
  60.         }
  61.         dp_current.swap(dp_next); // Move to the next column
  62.     }
  63.  
  64.     // Compute final answer
  65.     int answer = 0;
  66.     for (const auto& kv : dp_current) {
  67.         answer = (answer + kv.second) % MOD;
  68.     }
  69.  
  70.     cout << answer << endl;
  71.     return 0;
  72. }
  73.  
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
3 4
stdout
copy 
5
227
https://ideone.com/DbDHIq
language:
C++14 (gcc 8.3)
created:
59 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!