Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Hardbitmask-dp

Painting a Grid With Three Different Colors

Problem (restated)

Paint an m × n grid (m ≤ 5, n ≤ 1000) with 3 colors so every pair of edge-adjacent cells differs. Return the count modulo 10^9+7.

Intuition

The short side is the state. Encode a column as a base-3 integer (3^m ≤ 243). Keep only colorings with no two vertical neighbors equal, then DP across n columns using compatible pairs (no equal colors in the same row).

Approaches

Column-state DP

Unverified

Time O(n * 3^{2m})Space O(3^m)

Idea. Generate valid column encodings. Precompute adj[i] = encodings compatible with i. dp[state] = ways to paint the current column as state. Roll n-1 times. Mod on every add.

Walkthrough. m=1,n=1 → 3. m=1,n=2 → 6. m=5,n=5 → 580986.

Trade-offs. Valid states are 3·2^{m-1} (48 at m=5), not the full 243. Use long before mod in C#.

Solution

const MOD = 1_000_000_007;

export function colorTheGrid(m: number, n: number): number {
  const states: number[] = [];
  const gen = (pos: number, prev: number, enc: number): void => {
    if (pos === m) {
      states.push(enc);
      return;
    }
    for (let c = 0; c < 3; c++) {
      if (c !== prev) gen(pos + 1, c, enc * 3 + c);
    }
  };
  gen(0, -1, 0);
  const S = states.length;
  const compat = (a: number, b: number): boolean => {
    for (let i = 0; i < m; i++) {
      if (a % 3 === b % 3) return false;
      a = Math.floor(a / 3);
      b = Math.floor(b / 3);
    }
    return true;
  };
  const adj: number[][] = Array.from({ length: S }, () => []);
  for (let i = 0; i < S; i++) {
    for (let j = 0; j < S; j++) {
      if (compat(states[i]!, states[j]!)) adj[i]!.push(j);
    }
  }
  let dp = new Array<number>(S).fill(1);
  for (let col = 1; col < n; col++) {
    const ndp = new Array<number>(S).fill(0);
    for (let i = 0; i < S; i++) {
      const w = dp[i]!;
      if (!w) continue;
      for (const j of adj[i]!) ndp[j] = (ndp[j]! + w) % MOD;
    }
    dp = ndp;
  }
  let ans = 0;
  for (const v of dp) ans = (ans + v) % MOD;
  return ans;
}

const MOD = 1_000_000_007;

export function colorTheGrid(m: number, n: number): number {
  const states: number[] = [];
  const gen = (pos: number, prev: number, enc: number): void => {
    if (pos === m) {
      states.push(enc);
      return;
    }
    for (let c = 0; c < 3; c++) {
      if (c !== prev) gen(pos + 1, c, enc * 3 + c);
    }
  };
  gen(0, -1, 0);
  const S = states.length;
  const compat = (a: number, b: number): boolean => {
    for (let i = 0; i < m; i++) {
      if (a % 3 === b % 3) return false;
      a = Math.floor(a / 3);
      b = Math.floor(b / 3);
    }
    return true;
  };
  const adj: number[][] = Array.from({ length: S }, () => []);
  for (let i = 0; i < S; i++) {
    for (let j = 0; j < S; j++) {
      if (compat(states[i]!, states[j]!)) adj[i]!.push(j);
    }
  }
  let dp = new Array<number>(S).fill(1);
  for (let col = 1; col < n; col++) {
    const ndp = new Array<number>(S).fill(0);
    for (let i = 0; i < S; i++) {
      const w = dp[i]!;
      if (!w) continue;
      for (const j of adj[i]!) ndp[j] = (ndp[j]! + w) % MOD;
    }
    dp = ndp;
  }
  let ans = 0;
  for (const v of dp) ans = (ans + v) % MOD;
  return ans;
}

Template connection

Coloring bitmask DP: mask is a whole column (base-3, not bits), extra dimension is the previous column, transitions are the compatible list.

Reflection

A valid column coloring has different colors on adjacent rows. dp[state] is the number of ways to paint the current column as that state. Roll across compatible states n - 1 times.
Take the modulus on every add. m is at most 5 and there are 3 colors. Valid columns number 3 * 2**(m - 1), not every coloring in 3**m.
n = 1 only checks inside the column. m = 1 means adjacent columns use different colors.