Given the constraints where the grid height N is small (typically N ≤ 6) and the width M is large, a column-wise dynamic programming approach with state compression is the optimal strategy. The core challenge lies in efficiently tracking connectivity between cells across columns.
Initial DP Formulation and Limitations
A naive dynamic programming state might be defined as dp[i][mask][conn], where i represents the current column, mask represents the color configuration of the current column, and conn is a bitmask indicating which cells in the current column are connected to the top-left cell (1,1).
Transitions would involve enumerating the mask for the next column and updating connectivity using a Union-Find structure. However, this approach fails because connectivity is undirected. A cell might appear disconnected from (1,1) in the current sub-grid but becomes connected via a path that loops through future columns. Since standard DP processes columns sequentially from left to right, it cannot account for connectivity established by cells to the right, leading to incorrect state evaluations.
Refining the Connectivity State
To resolve the issue of future dependencies, the state definition must be adjusted. Instead of tracking connectivity to (1,1) globally, the DP state should track pairwise connectivity within the current profile. Specifically, for the cells in the current column, we need to know which cells belong to the same connected component relative to eachother.
Even with this adjustment, simply storing pairwise connectivity can be expensive. A robust method is to record, for each cell in the column, the distance to the next cell below it that shares the same connected component. If no such cell exists within the column, it implies the connection must happen through previous columns or the origin.
State Compression via Factorial Number System
Storing full pairwise connectivity matrices would require excessive memory. However, the connectivity pattern within a column of height N can be canonicalized. By recording the offset to the next connected row for each row, the state space can be compressed significantly.
For a column of height N, there are at most N! valid connectivity configurations. This allows us to map each configuration to a unique integer using a factorial number system. Specifically, for the i-th row, the value stored represents the offset to the next connected row. This value is bounded by the number of remaining rows, fitting perfectly into a mixed-radix system where the i-th digit has base i.
Transition Logic
The transitions between columns involve merging the connectivity information from the current column mask and the next column mask. This can be modeled using a Disjoint Set Union (DSU) structure. Since the transition logic depends only on the current mask, current connectivity state, and the next mask, it can be precomputed.
The algorithm proceeds as follows:
- Enumerate all valid color masks and connectivity encodings for a single column.
- Validate each encoding against the mask (e.g., adjacent cells of the same color must be connected).
- Precompute the transition table: for every valid state and every possible next mask, calculate the resulting connectivity encoding.
- Run the DP over the width M, accumulating counts modulo 10^9 + 7.
Complexity Analysis
The theoretical complexity involves the number of columns M, the number of masks 2^N, and the number of connectivity states (N+1)!. While the upper bound might appear high (approximately O(M · 4^N · (N+1)!)), the number of actually valid states is much smaller due to geometric constraints. Pruning invalid states during precomputation ensures the solution runs well within typical time limits.
Implementation
The following C++ implementation demonstrates the profile DP with factorial-based state compression. It precomputes valid configurations and transitions to optimize the main DP loop.
#include <iostream>
#include <vector>
#include <cstring>
#include <cassert>
using namespace std;
constexpr int MOD = 1000000007;
constexpr int MAX_H = 10;
constexpr int MAX_W = 110;
constexpr int MAX_STATES = 5040; // 7!
int H, W;
int factorials[MAX_H];
int memo_table[MAX_W][1 << 6][MAX_STATES];
bool valid_configuration[1 << 6][MAX_STATES];
int transition_table[1 << 6][MAX_STATES][1 << 6];
bool connected_to_origin[MAX_STATES];
struct DisjointSet {
int parent[MAX_H * 2];
void reset() {
memset(parent, 0, sizeof(parent));
}
int find(int x) {
if (parent[x] == 0) return x;
return parent[x] = find(parent[x]);
}
void unite(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
parent[rootX] = rootY;
}
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
if (!(cin >> H >> W)) return 0;
// Precompute factorials for state encoding
factorials[0] = 1;
for (int i = 1; i <= H + 1; ++i) {
factorials[i] = factorials[i - 1] * i;
}
// Initialize DP for the first column
for (int mask = 0; mask < (1 << H); ++mask) {
if (mask & 1) { // Top-left cell must be active
int state_id = factorials[H];
// Encode connectivity within the column
for (int r = 1; r < H; ++r) {
if ((mask & (1 << (r - 1))) && (mask & (1 << r))) {
state_id += factorials[H - r];
}
}
memo_table[1][mask][state_id] = 1;
}
}
// Precompute validity and transitions
for (int curr_mask = 0; curr_mask < (1 << H); ++curr_mask) {
for (int state_code = 0; state_code < factorials[H + 1]; ++state_code) {
vector<int> offsets;
int temp_code = state_code;
// Decode factorial number system
for (int i = 1; i <= H; ++i) {
offsets.push_back(temp_code % i);
temp_code /= i;
}
offsets.push_back(temp_code);
bool is_valid = true;
// Check consistency between mask and connectivity offsets
for (int r = 1; r < H; ++r) {
if ((curr_mask & (1 << (r - 1))) && (curr_mask & (1 << r))) {
if (offsets[H - r] != 1) is_valid = false;
}
}
for (int r = 1; r <= H; ++r) {
if (!(curr_mask & (1 << (r - 1))) && offsets[H - r] != 0) is_valid = false;
}
for (int r = 0; r <= H; ++r) {
if (offsets[H - r] && !(curr_mask & (1 << (r + offsets[H - r] - 1)))) is_valid = false;
}
valid_configuration[curr_mask][state_code] = is_valid;
if (!is_valid) continue;
// Precompute transitions for all possible next masks
for (int next_mask = 0; next_mask < (1 << H); ++next_mask) {
int &next_state = transition_table[curr_mask][state_code][next_mask];
DisjointSet dsu;
dsu.reset();
// Connect within current column based on state_code
for (int r = 0; r <= H; ++r) {
dsu.unite(r + 1, r + 1 + offsets[H - r]);
}
// Connect vertically between current and next column
for (int r = 1; r <= H; ++r) {
if ((curr_mask & (1 << (r - 1))) && (next_mask & (1 << (r - 1)))) {
dsu.unite(r + 1, r + 1 + H);
}
}
// Connect within next column
for (int r = 1; r < H; ++r) {
if ((next_mask & (1 << (r - 1))) && (next_mask & (1 << r))) {
dsu.unite(r + 1 + H, r + 2 + H);
}
}
// Re-encode connectivity for the next column
for (int r = H + 1; r <= 2 * H + 1; ++r) {
for (int k = r + 1; k <= 2 * H + 1; ++k) {
int rootR = dsu.find(r == H + 1 ? 1 : r);
int rootK = dsu.find(k);
if (rootR == rootK) {
assert(r != H + 1 || next_mask);
next_state += (k - r) * factorials[H - (r - H - 1)];
break;
}
}
}
}
// Check if this state implies connection to (1,1)
DisjointSet dsu_check;
dsu_check.reset();
for (int r = 0; r <= H; ++r) {
dsu_check.unite(r + 1, r + 1 + offsets[H - r]);
}
connected_to_origin[state_code] = (dsu_check.find(1) == dsu_check.find(H + 1));
}
}
// Run DP over columns
for (int col = 1; col < W; ++col) {
for (int curr_mask = 0; curr_mask < (1 << H); ++curr_mask) {
for (int state_code = 0; state_code < factorials[H + 1]; ++state_code) {
if (!valid_configuration[curr_mask][state_code]) continue;
int current_ways = memo_table[col][curr_mask][state_code];
if (current_ways == 0) continue;
for (int next_mask = 0; next_mask < (1 << H); ++next_mask) {
int next_state = transition_table[curr_mask][state_code][next_mask];
int &target = memo_table[col + 1][next_mask][next_state];
target += current_ways;
if (target >= MOD) target -= MOD;
}
}
}
}
// Sum up valid final states
int total_ans = 0;
for (int mask = 0; mask < (1 << H); ++mask) {
for (int state_code = 0; state_code < factorials[H + 1]; ++state_code) {
if (connected_to_origin[state_code]) {
total_ans += memo_table[W][mask][state_code];
if (total_ans >= MOD) total_ans -= MOD;
}
}
}
cout << total_ans << "\n";
return 0;
}