Number of Ways to Paint N x 3 Grid trong C++

Tô màu lưới n x 3 với 3 màu (Đỏ, Vàng, Xanh), không có 2 ô kề nhau (chung cạnh) cùng màu. Đếm số cách tô, modulo 10^9+7.

Ví dụ: n=1 → 12 cách. n=3 → 246 cách.

Giải thuật (DP trạng thái hàng)

Mỗi hàng có 2 loại pattern: 3 màu khác nhau (123) - 6 cách, hoặc 2 màu (121) - 6 cách. Chuyển trạng thái giữa các hàng:

• 121 → 121: 3 cách, 121 → 123: 2 cách
• 123 → 121: 2 cách, 123 → 123: 2 cách

Công thức truy hồi: a121' = 3*a121 + 2*a123; a123' = 2*a121 + 2*a123.

Ví dụ triển khai C++

#include <bits/stdc++.h>
using namespace std;
typedef long long lli;
const lli MOD = 1e9 + 7;

class Solution {
    lli add(lli a, lli b) { return (a + b) % MOD; }
public:
    int numOfWays(int n) {
        lli a121 = 6, a123 = 6;
        for (int i = 2; i <= n; i++) {
            lli b121 = add(3 * a121, 2 * a123);
            lli b123 = add(2 * a121, 2 * a123);
            a121 = b121;
            a123 = b123;
        }
        return add(a121, a123);
    }
};

int main() {
    Solution ob;
    cout << ob.numOfWays(3); // 246
    return 0;
}

Đầu vào / Đầu ra

Input: 3
Output: 246