Number of Ways to Paint N × 3 Grid

hard dynamic programming combinatorics modular arithmetic

Problem

Paint every cell of an n × 3 grid with one of three colors (Red, Yellow, Green) so that no two cells sharing a side have the same color. Return the number of valid colorings modulo 10⁹ + 7.

Inputn = 1

Output12

A single row of 3 cells has 3 · 2 · 2 = 12 valid colorings.

Inputn = 2

Output54

Each of the 12 first rows extends into either 5 or 4 second rows, giving 54 total.

n (number of rows, 1–30)

def num_of_ways(n):
    MOD = 10**9 + 7
    aba, abc = 6, 6          # rows of form ABA and ABC
    for _ in range(n - 1):
        aba, abc = (3 * aba + 2 * abc) % MOD, \
                   (2 * aba + 2 * abc) % MOD
    return (aba + abc) % MOD

function numOfWays(n) {
  const MOD = 1000000007n;
  let aba = 6n, abc = 6n;          // rows of form ABA and ABC
  for (let i = 1; i < n; i++) {
    const a = (3n * aba + 2n * abc) % MOD;
    const c = (2n * aba + 2n * abc) % MOD;
    aba = a; abc = c;
  }
  return Number((aba + abc) % MOD);
}

int numOfWays(int n) {
    long MOD = 1_000_000_007L;
    long aba = 6, abc = 6;          // rows of form ABA and ABC
    for (int i = 1; i < n; i++) {
        long a = (3 * aba + 2 * abc) % MOD;
        long c = (2 * aba + 2 * abc) % MOD;
        aba = a; abc = c;
    }
    return (int) ((aba + abc) % MOD);
}

int numOfWays(int n) {
    const long long MOD = 1000000007LL;
    long long aba = 6, abc = 6;     // rows of form ABA and ABC
    for (int i = 1; i < n; i++) {
        long long a = (3 * aba + 2 * abc) % MOD;
        long long c = (2 * aba + 2 * abc) % MOD;
        aba = a; abc = c;
    }
    return (int) ((aba + abc) % MOD);
}

Explanation

The whole grid is built one row at a time, so the only thing the next row depends on is the colors directly above it. That makes this a row-by-row dynamic programming problem where the “state” is the shape of the previous row.

A single valid row of three cells comes in exactly two shapes. An ABA row uses two colors with the ends matching (like 1·2·1) — there are 6 of these. An ABC row uses three distinct colors (like 1·2·3) — there are also 6. So a single row has 12 colorings, matching the n = 1 answer.

Now count how each shape extends downward. Above an ABA row you can place 3 valid ABA rows and 2 valid ABC rows. Above an ABC row you can place 2 ABA rows and 2 ABC rows. These constants come from checking which colorings differ from each cell above them.

That gives the recurrence aba' = 3·aba + 2·abc and abc' = 2·aba + 2·abc. Start with aba = abc = 6 and apply it n − 1 times; the answer is (aba + abc) mod (10⁹ + 7).

Only two numbers are carried between rows, so the loop runs in O(n) time and O(1) space. Every product and sum is reduced modulo 10⁹ + 7 to keep the values from overflowing.

Time: O(n) Space: O(1)