Số cách tô màu lưới N × 3 trong C++

Cho lưới kích thước n x 3, cần tô mỗi ô bằng đúng một trong ba màu: Đỏ, Vàng, Xanh lá. Điều kiện: không có hai ô liền kề cùng màu. Tìm số cách tô màu, kết quả modulo 10^9 + 7.

Ví dụ: n = 1 → Kết quả = 12

Phương pháp giải

Phân loại hàng thành 2 loại: 3 màu khác nhau (123) và 2 màu (121). Công thức truy hồi:

a123' = 2*a121 + 2*a123
a121' = 3*a121 + 2*a123

Khởi tạo a123 = 6, a121 = 6. Lặp n-1 lần.

Ví dụ chương trình

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

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

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

Số cách tô màu lưới N × 3 trong C++

Phương pháp giải

Ví dụ chương trình

Đầu vào

Đầu ra